249 lines
12 KiB
BibTeX
249 lines
12 KiB
BibTeX
@inproceedings{DBLP:conf/sigmod/ZhouXSNMTABSLRD21,
|
||
author = {Jingyu Zhou and
|
||
Meng Xu and
|
||
Alexander Shraer and
|
||
Bala Namasivayam and
|
||
Alex Miller and
|
||
Evan Tschannen and
|
||
Steve Atherton and
|
||
Andrew J. Beamon and
|
||
Rusty Sears and
|
||
John Leach and
|
||
Dave Rosenthal and
|
||
Xin Dong and
|
||
Will Wilson and
|
||
Ben Collins and
|
||
David Scherer and
|
||
Alec Grieser and
|
||
Young Liu and
|
||
Alvin Moore and
|
||
Bhaskar Muppana and
|
||
Xiaoge Su and
|
||
Vishesh Yadav},
|
||
editor = {Guoliang Li and
|
||
Zhanhuai Li and
|
||
Stratos Idreos and
|
||
Divesh Srivastava},
|
||
title = {FoundationDB: {A} Distributed Unbundled Transactional Key Value Store},
|
||
booktitle = {{SIGMOD} '21: International Conference on Management of Data, Virtual
|
||
Event, China, June 20-25, 2021},
|
||
pages = {2653--2666},
|
||
publisher = {{ACM}},
|
||
year = {2021},
|
||
url = {https://doi.org/10.1145/3448016.3457559},
|
||
doi = {10.1145/3448016.3457559},
|
||
timestamp = {Tue, 31 Oct 2023 15:43:39 +0100},
|
||
biburl = {https://dblp.org/rec/conf/sigmod/ZhouXSNMTABSLRD21.bib},
|
||
bibsource = {dblp computer science bibliography, https://dblp.org}
|
||
}
|
||
|
||
@article{10.1145/78973.78977,
|
||
author = {Pugh, William},
|
||
title = {Skip lists: a probabilistic alternative to balanced trees},
|
||
year = {1990},
|
||
issue_date = {June 1990},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
volume = {33},
|
||
number = {6},
|
||
issn = {0001-0782},
|
||
url = {https://doi.org/10.1145/78973.78977},
|
||
doi = {10.1145/78973.78977},
|
||
abstract = {Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.},
|
||
journal = {Commun. ACM},
|
||
month = {6},
|
||
pages = {668-676},
|
||
numpages = {9},
|
||
keywords = {data structures, searching, trees}
|
||
}
|
||
|
||
@inproceedings{DBLP:conf/icde/LeisK013,
|
||
author = {Viktor Leis and
|
||
Alfons Kemper and
|
||
Thomas Neumann},
|
||
editor = {Christian S. Jensen and
|
||
Christopher M. Jermaine and
|
||
Xiaofang Zhou},
|
||
title = {The adaptive radix tree: ARTful indexing for main-memory databases},
|
||
booktitle = {29th {IEEE} International Conference on Data Engineering, {ICDE} 2013,
|
||
Brisbane, Australia, April 8-12, 2013},
|
||
pages = {38--49},
|
||
publisher = {{IEEE} Computer Society},
|
||
year = {2013},
|
||
url = {https://doi.org/10.1109/ICDE.2013.6544812},
|
||
doi = {10.1109/ICDE.2013.6544812},
|
||
timestamp = {Fri, 24 Mar 2023 00:00:01 +0100},
|
||
biburl = {https://dblp.org/rec/conf/icde/LeisK013.bib},
|
||
bibsource = {dblp computer science bibliography, https://dblp.org}
|
||
}
|
||
|
||
@book{cormen2022introduction,
|
||
title={Introduction to algorithms},
|
||
author={Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford},
|
||
year={2022},
|
||
publisher={MIT press},
|
||
chapter={17 Augmenting Data Structures}
|
||
}
|
||
|
||
@article{bentley1979decomposable,
|
||
title={Decomposable searching problems},
|
||
author={Bentley, Jon Louis and others},
|
||
journal={Inf. Process. Lett.},
|
||
volume={8},
|
||
number={5},
|
||
pages={244--251},
|
||
year={1979}
|
||
}
|
||
|
||
@inproceedings{adelson1962algorithm,
|
||
title={An algorithm for organization of information},
|
||
author={Adelson-Velskii, Georgii Maksimovich and Landis, Evgenii Mikhailovich},
|
||
booktitle={Doklady Akademii Nauk},
|
||
volume={146},
|
||
number={2},
|
||
pages={263--266},
|
||
year={1962},
|
||
organization={Russian Academy of Sciences}
|
||
}
|
||
|
||
@inproceedings{guibas1978dichromatic,
|
||
title={A dichromatic framework for balanced trees},
|
||
author={Guibas, Leo J and Sedgewick, Robert},
|
||
booktitle={19th Annual Symposium on Foundations of Computer Science (sfcs 1978)},
|
||
pages={8--21},
|
||
year={1978},
|
||
organization={IEEE}
|
||
}
|
||
|
||
@article{seidel1996randomized,
|
||
title={Randomized search trees},
|
||
author={Seidel, Raimund and Aragon, Cecilia R},
|
||
journal={Algorithmica},
|
||
volume={16},
|
||
number={4-5},
|
||
pages={464--497},
|
||
year={1996},
|
||
publisher={Springer}
|
||
}
|
||
|
||
@article{comer1979ubiquitous,
|
||
title={Ubiquitous B-tree},
|
||
author={Comer, Douglas},
|
||
journal={ACM Computing Surveys (CSUR)},
|
||
volume={11},
|
||
number={2},
|
||
pages={121--137},
|
||
year={1979},
|
||
publisher={ACM New York, NY, USA}
|
||
}
|
||
|
||
@inproceedings{binna2018hot,
|
||
title={HOT: A height optimized trie index for main-memory database systems},
|
||
author={Binna, Robert and Zangerle, Eva and Pichl, Martin and Specht, G{\"u}nther and Leis, Viktor},
|
||
booktitle={Proceedings of the 2018 International Conference on Management of Data},
|
||
pages={521--534},
|
||
year={2018}
|
||
}
|
||
|
||
@article{kung1981optimistic,
|
||
title={On optimistic methods for concurrency control},
|
||
author={Kung, Hsiang-Tsung and Robinson, John T},
|
||
journal={ACM Transactions on Database Systems (TODS)},
|
||
volume={6},
|
||
number={2},
|
||
pages={213--226},
|
||
year={1981},
|
||
publisher={ACM New York, NY, USA}
|
||
}
|
||
|
||
@article{Lemire_2018,
|
||
title={Roaring bitmaps: Implementation of an optimized software library},
|
||
volume={48},
|
||
ISSN={1097-024X},
|
||
url={http://dx.doi.org/10.1002/spe.2560},
|
||
DOI={10.1002/spe.2560},
|
||
number={4},
|
||
journal={Software: Practice and Experience},
|
||
publisher={Wiley},
|
||
author={Lemire, Daniel and Kaser, Owen and Kurz, Nathan and Deri, Luca and O’Hara, Chris and Saint‐Jacques, François and Ssi‐Yan‐Kai, Gregory},
|
||
year={2018},
|
||
month=jan, pages={867–895} }
|
||
|
||
@misc{libfuzzer,
|
||
title = {libFuzzer – a library for coverage-guided fuzz testing},
|
||
howpublished = {\url{https://llvm.org/docs/LibFuzzer.html}},
|
||
note = {Accessed: 2024-04-19}
|
||
}
|
||
|
||
@misc{ubsan,
|
||
title = {UndefinedBehaviorSanitizer — Clang 19.0.0git documentation},
|
||
howpublished = {\url{https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html}},
|
||
note = {Accessed: 2024-04-19}
|
||
}
|
||
|
||
|
||
@inproceedings{10.5555/2342821.2342849,
|
||
author = {Serebryany, Konstantin and Bruening, Derek and Potapenko, Alexander and Vyukov, Dmitry},
|
||
title = {AddressSanitizer: a fast address sanity checker},
|
||
year = {2012},
|
||
publisher = {USENIX Association},
|
||
address = {USA},
|
||
abstract = {Memory access bugs, including buffer overflows and uses of freed heap memory, remain a serious problem for programming languages like C and C++. Many memory error detectors exist, but most of them are either slow or detect a limited set of bugs, or both.This paper presents AddressSanitizer, a new memory error detector. Our tool finds out-of-bounds accesses to heap, stack, and global objects, as well as use-after-free bugs. It employs a specialized memory allocator and code instrumentation that is simple enough to be implemented in any compiler, binary translation system, or even in hardware.AddressSanitizer achieves efficiency without sacrificing comprehensiveness. Its average slowdown is just 73\% yet it accurately detects bugs at the point of occurrence. It has found over 300 previously unknown bugs in the Chromium browser and many bugs in other software.},
|
||
booktitle = {Proceedings of the 2012 USENIX Conference on Annual Technical Conference},
|
||
pages = {28},
|
||
numpages = {1},
|
||
location = {Boston, MA},
|
||
series = {USENIX ATC'12}
|
||
}
|
||
@inproceedings{10.1145/1791194.1791203,
|
||
author = {Serebryany, Konstantin and Iskhodzhanov, Timur},
|
||
title = {ThreadSanitizer: data race detection in practice},
|
||
year = {2009},
|
||
isbn = {9781605587936},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
url = {https://doi.org/10.1145/1791194.1791203},
|
||
doi = {10.1145/1791194.1791203},
|
||
abstract = {Data races are a particularly unpleasant kind of threading bugs. They are hard to find and reproduce -- you may not observe a bug during the entire testing cycle and will only see it in production as rare unexplainable failures. This paper presents ThreadSanitizer -- a dynamic detector of data races. We describe the hybrid algorithm (based on happens-before and locksets) used in the detector. We introduce what we call dynamic annotations -- a sort of race detection API that allows a user to inform the detector about any tricky synchronization in the user program. Various practical aspects of using ThreadSanitizer for testing multithreaded C++ code at Google are also discussed.},
|
||
booktitle = {Proceedings of the Workshop on Binary Instrumentation and Applications},
|
||
pages = {62–71},
|
||
numpages = {10},
|
||
keywords = {Valgrind, concurrency bugs, dynamic data race detection, testing},
|
||
location = {New York, New York, USA},
|
||
series = {WBIA '09}
|
||
}
|
||
|
||
@article{10.1145/3591257,
|
||
author = {Isemann, Raphael and Giuffrida, Cristiano and Bos, Herbert and van der Kouwe, Erik and Gleissenthall, Klaus von},
|
||
title = {Don’t Look UB: Exposing Sanitizer-Eliding Compiler Optimizations},
|
||
year = {2023},
|
||
issue_date = {June 2023},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
volume = {7},
|
||
number = {PLDI},
|
||
url = {https://doi.org/10.1145/3591257},
|
||
doi = {10.1145/3591257},
|
||
abstract = {Sanitizers are widely used compiler features that detect undefined behavior and resulting vulnerabilities by injecting runtime checks into programs. For better performance, sanitizers are often used in conjunction with optimization passes. But doing so combines two compiler features with conflicting objectives. While sanitizers want to expose undefined behavior, optimizers often exploit these same properties for performance. In this paper, we show that this clash can have serious consequences: optimizations can remove sanitizer failures, thereby hiding the presence of bugs or even introducing new ones.
|
||
|
||
We present LookUB, a differential-testing based framework for finding optimizer transformations that elide sanitizer failures. We used our method to find 17 such sanitizer-eliding optimizations in Clang. Next, we used static analysis and fuzzing to search for bugs in open-source projects that were previously hidden due to sanitizer-eliding optimizations. This led us to discover 20 new bugs in Linux Containers, libmpeg2, NTFS-3G, and WINE. Finally, we present an effective mitigation strategy based on a customization of the Clang optimizer with an overhead increase of 4\%.},
|
||
journal = {Proc. ACM Program. Lang.},
|
||
month = {jun},
|
||
articleno = {143},
|
||
numpages = {21},
|
||
keywords = {Sanitizers, Optimizations, Fuzzing}
|
||
}
|
||
|
||
@inproceedings{10.5555/1247360.1247362,
|
||
author = {Seward, Julian and Nethercote, Nicholas},
|
||
title = {Using Valgrind to detect undefined value errors with bit-precision},
|
||
year = {2005},
|
||
publisher = {USENIX Association},
|
||
address = {USA},
|
||
abstract = {We present Memcheck, a tool that has been implemented with the dynamic binary instrumentation framework Valgrind. Memcheck detects a wide range of memory errors in programs as they run. This paper focuses on one kind of error that Memcheck detects: undefined value errors. Such errors are common, and often cause bugs that are hard to find in programs written in languages such as C, C++ and Fortran. Memcheck's definedness checking improves on that of previous tools by being accurate to the level of individual bits. This accuracy gives Memcheck a low false positive and false negative rate.The definedness checking involves shadowing every bit of data in registers and memory with a second bit that indicates if the bit has a defined value. Every value-creating operation is instrumented with a shadow operation that propagates shadow bits appropriately. Memcheck uses these shadow bits to detect uses of undefined values that could adversely affect a program's behaviour.Under Memcheck, programs typically run 20-30 times slower than normal. This is fast enough to use with large programs. Memcheck finds many errors in real programs, and has been used during the past two years by thousands of programmers on a wide range of systems, including OpenOffice, Mozilla, Opera, KDE, GNOME, MySQL, Perl, Samba, The GIMP, and Unreal Tournament.},
|
||
booktitle = {Proceedings of the Annual Conference on USENIX Annual Technical Conference},
|
||
pages = {2},
|
||
numpages = {1},
|
||
location = {Anaheim, CA},
|
||
series = {ATEC '05}
|
||
} |