Automatic generation of library bindings using static analysis

ABSTRACT

High-level languages are growing in popularity. However, decades of C software development have produced large libraries of fast, time-tested, meritorious code that are impractical to recreate from scratch. Cross-language bindings can expose low-level C code to high-level languages. Unfortunately, writing bindings by hand is tedious and error-prone, while mainstream binding generators require extensive manual annotation or fail to offer the language features that users of modern languages have come to expect.

We present an improved binding-generation strategy based on static analysis of unannotated library source code. We characterize three high-level idioms that are not uniquely expressible in C's low-level type system: array parameters, resource managers, and multiple return values. We describe a suite of interprocedural analyses that recover this high-level information, and we show how the results can be used in a binding generator for the Python programming language. In experiments with four large C libraries, we find that our approach avoids the mistakes characteristic of hand-written bindings while offering a level of Python integration unmatched by prior automated approaches. Among the thousands of functions in the public interfaces of these libraries, roughly 40% exhibit the behaviors detected by our static analyses.

REFERENCES

• 1: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 2: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, Department of Computer Science, University of Cophenhagen, May 1994.
• 3: David M. Beazley, SWIG: an easy to use tool for integrating scripting languages with C and C++, Proceedings of the 4th conference on USENIX Tcl/Tk Workshop, 1996, p.15-15, July 10-13, 1996, Monterey, California
• 4: D. M. Beazley. Simplified wrapper and interface generator. http://www.swig.org, Nov. 2008.
• 5: E. Busboom, A. Cancro, and W. Goesgens. libical. http://freeassociation.sourceforge.net/, Nov. 2008.
• 6: Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
• 7: Ctypesgen Developers. ctypesgen. http://code.google.com/p/ctypesgen/, Nov. 2008.
• 8: Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.36-45, June 21-25, 1993, Albuquerque, New Mexico, United States
• 9: M. Elder, S. Jackson, and B. Liblit. Code sandwiches. Technical Report 1647, University of Wisconsin-Madison, Oct. 2008.
• 10: Jeffrey S. Foster , Robert Johnson , John Kodumal , Alex Aiken, Flow-insensitive type qualifiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.1035-1087, November 2006 [doi>10.1145/1186632.1186635]
• 11: Michael Furr , Jeffrey S. Foster, Checking type safety of foreign function calls, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 12: J. Gailly and M. Adler. zlib home site. http://zlib.net/, Nov. 2008.
• 13: M. Galassi, J. Davies, J. Theiler, B. Gough, G. Jungman, M. Booth, and F. Rossi. GNU Scientific Library Reference Manual. Network Theory Ltd., Bristol, United Kingdom, revised second edition, Aug. 2006.
• 14: The GNOME Project. GNOME Bug Tracking System. http://bugzilla.gnome.org, Jan. 2009.
• 15: Haryadi S. Gunawi , Cindy Rubio-González , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dussea , Ben Liblit, EIO: error handling is occasionally correct, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-16, February 26-29, 2008, San Jose, California
• 16: Mary Jean Harrold , Mary Lou Soffa, Efficient computation of interprocedural definition-use chains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.175-204, March 1994 [doi>10.1145/174662.174663]
• 17: David L. Heine , Monica S. Lam, A practical flow-sensitive and context-sensitive C and C++ memory leak detector, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 18: T. Heller. ctypeslib -- useful additions to the ctypes FFI library. http://pypi.python.org/pypi/ctypeslib/, Nov. 2008.
• 19: S. Jaroszewicz. ctypesGSL. http://www.cs.umb.edu/sj/ctypesGsl/, Aug. 2008.
• 20: T. Kientzle. libarchive. http://people.freebsd.org/~kientzle/libarchive/, Nov. 2008.
• 21: Ted Kremenek , Paul Twohey , Godmar Back , Andrew Ng , Dawson Engler, From uncertainty to belief: inferring the specification within, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 22: C. Lattner. LLVM and Clang: Next generation compiler technology. In BSDCan 2008: The BSD Conference, Ottawa, Canada, May 2008.
• 23: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 24: A. Makhorin. GLPK (GNU linear programming kit). http://www.gnu.org/software/glpk/, Nov. 2008.
• 25: M.-T. Pham. ctypes-glpk: A Python wrapper for GLPK using ctypes. http://code.google.com/p/ctypes-glpk, Nov. 2008.
• 26: John Reppy , Chunyan Song, Application-specific foreign-interface generation, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1173706.1173714]
• 27: Cindy Rubio-González , Haryadi S. Gunawi , Ben Liblit , Remzi H. Arpaci-Dusseau , Andrea C. Arpaci-Dusseau, Error propagation analysis for file systems, Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, June 15-21, 2009, Dublin, Ireland
• 28: J. Seward. bzip2. http://www.bzip.org/, Nov. 2008.
• 29: Silicon Graphics, Inc. libacl. http://oss.sgi.com/projects/xfs/, Feb. 2008.
• 30: Silicon Graphics, Inc. libattr. http://oss.sgi.com/projects/xfs/, Feb. 2008.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Experimentation, Human Factors, Languages, Reliability

Keywords:
bindings, dataflow analysis, ffi, foreign function interfaces, multi-language code reuse, static library analysis