Dispersing proprietary applications as benchmarks through code mutation

ABSTRACT

Industry vendors hesitate to disseminate proprietary applications to academia and third party vendors. By consequence, the benchmarking process is typically driven by standardized, open-source benchmarks which may be very different from and likely not representative of the real-life applications of interest.

This paper proposes code mutation, a novel technique that mutates a proprietary application to complicate reverse engineering so that it can be distributed as a benchmark. The benchmark mutant then serves as a proxy for the proprietary application. The key idea in the proposed code mutation approach is to preserve the proprietary application's dynamic memory access and/or control flow behavior in the benchmark mutant while mutating the rest of the application code. To this end, we compute program slices for memory access operations and/or control flow operationstrimmed through constant value and branch profiles; and subsequently mutate the instructions not appearing in these slices through binary rewriting.

Our experimental results using SPEC CPU2000 and MiBench benchmarks show that code mutation is a promising technique that mutates up to 90% of the static binary, up to 50% of the dynamically executed instructions, and up to 35% of the at run time exposed inter-operation data dependencies. The performance characteristics of the mutant are very similar to those of the proprietary application across a wide range of microarchitectures and hardware implementations.

REFERENCES

• 1: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 2: Robert H. Bell, Jr. , Lizy K. John, Improved automatic testcase synthesis for performance model validation, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088164]
• 3: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 4: C. Collberg, C. Thomborson, and D. Low. A taxonomy of obfuscating transformations. Technical Report 148, The University of Auckland, July 1997.
• 5: Thomas M. Conte , Mary Ann Hirsch , Kishore N. Menezes, Reducing State Loss For Effective Trace Sampling of Superscalar Processors, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.468-477, October 07-09, 1996
• 6: H. J. Curnow and B. A. Wichmann. A synthetic benchmark. The Computer Journal, 19(1):43--49, 1976.
• 7: Bruno De Bus , Daniel Kästner , Dominique Chanet , Ludo Van Put , Bjorn De Sutter, Post-pass compaction techniques, Communications of the ACM, v.46 n.8, August 2003 [doi>10.1145/859670.859696]
• 8: Lieven Eeckhout , Robert H. Bell Jr. , Bastiaan Stougie , Koen De Bosschere , Lizy K. John, Control Flow Modeling in Statistical Simulation for Accurate and Efficient Processor Design Studies, Proceedings of the 31st annual international symposium on Computer architecture, p.350, June 19-23, 2004, München, Germany
• 9: Jun Ge , Soma Chaudhuri , Akhilesh Tyagi, Control flow based obfuscation, Proceedings of the 5th ACM workshop on Digital rights management, November 07-07, 2005, Alexandria, VA, USA [doi>10.1145/1102546.1102561]
• 10: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 11: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 12: Kenneth Hoste , Aashish Phansalkar , Lieven Eeckhout , Andy Georges , Lizy K. John , Koen De Bosschere, Performance prediction based on inherent program similarity, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152174]
• 13: C. Hsieh and M. Pedram. Micro-processor power estimation using profile-driven program synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(11):1080--1089, Nov. 1998.
• 14: Vijay S. Iyengar , Louise H. Trevillyan , Pradip Bose, Representative Traces for Processor Models with Infinite Cache, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.62, February 03-07, 1996
• 15: A. M. Joshi, L. Eeckhout, R. H. Bell Jr., and L. K. John. Performance cloning: A technique for disseminating proprietary applications as benchmarks. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC), pages 105--115, Oct. 2006.
• 16: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 17: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 18: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 19: Satish Narayanasamy , Cristiano Pereira , Harish Patil , Robert Cohn , Brad Calder, Automatic logging of operating system effects to guide application-level architecture simulation, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 20: Sébastien Nussbaum , James E. Smith, Modeling Superscalar Processors via Statistical Simulation, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.15-24, September 08-12, 2001
• 21: Mark Oskin , Frederic T. Chong , Matthew Farrens, HLS: combining statistical and symbolic simulation to guide microprocessor designs, Proceedings of the 27th annual international symposium on Computer architecture, p.71-82, June 2000, Vancouver, British Columbia, Canada
• 22: J. Ringenberg , C. Pelosi , D. Oehmke , T. Mudge, Intrinsic Checkpointing: A Methodology for Decreasing Simulation Time Through Binary Modification, Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, p.78-88, March 20-22, 2005 [doi>10.1109/ISPASS.2005.1430561]
• 23: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 24: Kevin Skadron , Margaret Martonosi , David I. August , Mark D. Hill , David J. Lilja , Vijay S. Pai, Challenges in Computer Architecture Evaluation, Computer, v.36 n.8, p.30-36, August 2003 [doi>10.1109/MC.2003.1220579]
• 25: A. Srivastava and A. Eustace. ATOM: A system for building customized program analysis tools. Technical Report 94/2, Western Research Lab, Compaq, Mar. 1994.
• 26: F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3):121--189, 1995.
• 27: Reinhold P. Weicker, Dhrystone: a synthetic systems programming benchmark, Communications of the ACM, v.27 n.10, p.1013-1030, Oct 1984 [doi>10.1145/358274.358283]
• 28: M. Weiser. Program slicing. IEEE Transaction on Software Engineering, 10(4):352--357, July 1984.
• 29: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 30: M. T. Yourst. PTLsim: A cycle accurate full system x86-64 microarchitectural simulator. In Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 23--34, Apr. 2007.
• 31: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Cost and precision tradeoffs of dynamic data slicing algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.631-661, July 2005 [doi>10.1145/1075382.1075384]
• 32: Craig B. Zilles , Gurindar S. Sohi, Understanding the backward slices of performance degrading instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.172-181, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Experimentation, Measurement, Performance

Keywords:
benchmark generation, code mutation