Abstract: I will present our Sparrow system, an industrial-strength static analysis system that finds common bugs such as buffer overrun, memory leak, unll dereference, etc. in C code. From the elusive three in static analysis (deep property, scalability, automation), Sparrow lets go of deep properties, yet achieves the other two and, in addition, targets non-domain-specific C programs.

As of its performance, in comparison with other published memory leak detectors for example, Sparrow detects consistently more number of bugs for the same published benchmarks, having the biggest efficacy score: number of true alarms per KLOC * 1/false alarm ratio. Sparrow's speed is 785LOC/sec in average.

Sparrow's analysis engine is a combination of a sound abstract interpreter with a collection of unsound catalysts. The combination is in order to strike a cost-accuracy balance in realistic setting. The sound abstract interpreter is non-relational, context insensitive, and path insensitive: simple and scalable but inaccurate. The unsound catalysts are sparsely used to enhance the analysis accuracy. Relationality and path-sensitivity are achieved for relevant areas of the input code by selective loop unrolling and effect-path-domination. Context sensitivity is achieved by procedural, parameterized summarizations and their instantiations at call cites.

This is a co-work with the graduate students of our Programming Research Laboratory: Y. Jhee, M. Jin, Y. Jung, D. Kim, S. Kong, H. Lee, H. Oh, and D. Park.

Kwangkeun Yi is a full professor in Seoul National University. He holds a doctorate in computer science from University of Illinois at Urbana-Champaign(1993) and bachelor's in computer science and statistics from Seoul National University(1987). After his Ph.D. he worked as a Member of Technical Staff at the Software Principles Research Department in Bell Labs for 2 years. Then he joined, as an assistant professor, Korea Advanced Institute of Science and Technology. In 2003 he moved to Seoul National University. Appointments: dcm@cs.cmu.edu