More Like this

1. On the Naturalness of Fuzzer-Generated Code

   https://doi.org/10.1145/3524842.3527972  

   Kambhamettu, Rajeswari Hita ; Billos, John ; Oluwaseun-Apo, Tomi ; Gafford, Benjamin ; Padhye, Rohan ; Hellendoorn, Vincent J. ( May 2022 , 19th International Conference on Mining Software Repositories)

   Compiler fuzzing tools such as Csmith have uncovered many bugs in compilers by randomly sampling programs from a generative model. The success of these tools is often attributed to their ability to generate unexpected corner case inputs that developers tend to overlook during manual testing. At the same time, their chaotic nature makes fuzzer-generated test cases notoriously hard to interpret, which has lead to the creation of input simplification tools such as C-Reduce (for C compiler bugs). In until now unrelated work, researchers have also shown that human-written software tends to be rather repetitive and predictable to language models. Studies show that developers deliberately write more predictable code, whereas code with bugs is relatively unpredictable. In this study, we ask the natural questions of whether this high predictability property of code also, and perhaps counter-intuitively, applies to fuzzer-generated code. That is, we investigate whether fuzzer-generated compiler inputs are deemed unpredictable by a language model built on human-written code and surprisingly conclude that it is not. To the contrary, Csmith fuzzer-generated programs are more predictable on a per-token basis than human-written C programs. Furthermore, bug-triggering tended to be more predictable still than random inputs, and the C-Reduce minimization tool did not substantially increase this predictability. Rather, we find that bug-triggering inputs are unpredictable relative to Csmith's own generative model. This is encouraging; our results suggest promising research directions on incorporating predictability metrics in the fuzzing and reduction tools themselves. 

   more » « less
2. DSGEN: concolic testing GPU implementations of concurrent dynamic data structures

   https://doi.org/10.1145/3447818.3460962  

   Sun, Xiaofan ; Gupta, Rajiv ( June 2021 , ICS '21: Proceedings of the ACM International Conference on Supercomputing)

   null (Ed.)

   Concolic testing combines concrete execution with symbolic execution along the executed path to automatically generate new test inputs that exercise program paths and deliver high code coverage during testing. The GKLEE tool uses this approach to expose data races in CUDA programs written for execution of GPGPUs. In programs employing concurrent dynamic data structures, automatic generation of data structures with appropriate shapes that cause threads to follow selected, possibly divergent, paths is a challenge. Moreover, a single non-conflicting data structure must be generated for multiple threads, that is, a single shape must be found that simultaneously causes all threads to follow their respective chosen paths. When an execution exposes a bug (e.g., a data race), the generated data structure shape helps the programmer understand the cause of the bug. Because GKLEE does not permit pointers that construct dynamic data structures to be made symbolic, it cannot automatically generate data structures of different shapes and must rely on the user to write code that constructs them to exercise desired paths. We have developed DSGEN for automatically generating non-conflicting dynamic data structures with different shapes and integrated it with GKLEE to uncover and facilitate understanding of data races in programs that employ complex concurrent dynamic data structures. In comparison to GKLEE, DSGEN increases the number of races detected from 10 to 25 by automatically generating a total of 1,897 shapes in implementations of four complex concurrent dynamic data structures -- B-Tree, Hash-Array Mapped Trie, RRB-Tree, and Skip List. 

   more » « less
3. The Indigo Program-Verification Microbenchmark Suite of Irregular Parallel Code Patterns

   https://doi.org/10.1109/ISPASS55109.2022.00003  

   Liu, Yiqian ; Azami, Noushin ; Walters, Corbin ; Burtscher, Martin ( May 2022 , 2022 IEEE International Symposium on Performance Analysis of Systems and Software)

   Irregular programs are found in many domains and tend to exhibit input-dependent control flow and memory accesses. This paper introduces the Indigo suite of important irregular parallel code patterns for testing verification and other tools. We studied many irregular CPU and GPU programs and extracted the key code patterns. Then, we methodically built variations of these patterns to alter the control-flow and memory-access behavior and/or introduce bugs, yielding the thousands of OpenMP and CUDA microbenchmarks in the suite. Indigo includes a set of generators to systematically create an unbounded number of inputs for each microbenchmark, which is essential to exercise the wide range of possible behaviors of input-dependent codes. To manage the millions of code and input combinations, Indigo provides the flexibility to generate user-defined subsets of the suite. Experiments with a subset of buggy and bug-free codes illustrate that irregular programs pose a significant challenge to both static and dynamic program verification tools. Moreover, such tools can perform quite differently across code patterns that contain the same bug. 

   more » « less
4. Dynamic Inference of Likely Metamorphic Properties to Support Differential Testing

   https://doi.org/10.1109/AST.2015.19  

   Su, Fang-Hsiang ; Bell, Jonathan ; Murphy, Christian ; Kaiser, Gail ( May 2015 , 10th IEEE/ACM International Workshop on Automation of Software Test (AST))

   Metamorphic testing is an advanced technique to test programs without a true test oracle such as machine learning applications. Because these programs have no general oracle to identify their correctness, traditional testing techniques such as unit testing may not be helpful for developers to detect potential bugs. This paper presents a novel system, KABU, which can dynamically infer properties of methods' states in programs that describe the characteristics of a method before and after transforming its input. These Metamorphic Properties (MPs) are pivotal to detecting potential bugs in programs without test oracles, but most previous work relies solely on human effort to identify them and only considers MPs between input parameters and output result (return value) of a program or method. This paper also proposes a testing concept, Metamorphic Differential Testing (MDT). By detecting different sets of MPs between different versions for the same method, KABU reports potential bugs for human review. We have performed a preliminary evaluation of KABU by comparing the MPs detected by humans with the MPs detected by KABU. Our preliminary results are promising: KABU can find more MPs than human developers, and MDT is effective at detecting function changes in methods. 

   more » « less
5. Verifying Static Analysis Tools (Extended abstract)

   Udaya Sathiyamoorthy ; Tiago Cogumbreiro ( January 2023 , International Symposium on Trends in Functional Programming)

   We present a technique to stress-test the correctness of static analysis tools for CUDA programs, involving code generation and fixed point analysis. Our method revolves around a family of behavioral types called memory access protocols (MAPs), an abstraction used by Faial to determine whether CUDA programs are data-race free. In this paper, we introduce a code generation technique to represent MAPs in a form comprehensible to static analyzers (CUDA code). We use fixed point analysis to detect consistency errors in how programs are represented. We perform white-box testing with Faial, a tool we are already familiar with, to simultaneously fix bugs and facilitate further testing. 

   more » « less