Program Lifting using Gray-Box Behavior

Bruce Collie, Michael F.P. O'Boyle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Porting specialized application components to new platforms is difficult. This is particularly true if the components depend on proprietary libraries, or specific hardware. To tackle this, existing work has sought to recover high-level descriptions of application components to ease their retargeting. However, existing schemes are either too limited, targeting just one application domain, or too weak, making them ill-suited to recovering real-world programs. Additionally, many rely on help in the form of problem-specific user annotations or complex specifications. This paper develops a new approach using gray-box program synthesis, which recovers code by automatically constructing a program to match the behavior of an unknown component. However, unlike other synthesis approaches, it exploits the dynamic or gray-box behavior of a component to guide recovery. For example, the execution time, memory access patterns or observed instruction traces can all be used to direct synthesis. We evaluate our technique (HAZE) extensively against existing program synthesizers and a domain-specific lifter. Our scheme is able to generalize effectively across domains, synthesizing and lifting more programs than prior techniques, without any external assistance. We validate our methodology using bounded model checking, demonstrating that our synthesized programs are correct. Finally, we apply our approach to machine learning workloads, obtaining significant speedups automatically.
Original languageEnglish
Title of host publicationProceedings of 30th International Conference on Parallel Architectures and Compilation Techniques (PACT 2021)
EditorsJaejin Lee, Albert Cohen
PublisherIEEE
Pages60-74
Number of pages15
ISBN (Electronic)978-1-6654-4278-7
ISBN (Print)978-1-6654-4279-4
DOIs
Publication statusPublished - 18 Oct 2021
Event2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT) - Atlanta, GA, USA
Duration: 26 Sept 202129 Sept 2021

Conference

Conference2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT)
Period26/09/2129/09/21

Keywords / Materials (for Non-textual outputs)

  • 30th International Conference on Parallel Architectures and Compilation Techniques
  • lifting
  • compilers

Fingerprint

Dive into the research topics of 'Program Lifting using Gray-Box Behavior'. Together they form a unique fingerprint.

Cite this