subject:(Optimal program synthesis)

You searched for subject:(Optimal program synthesis). One record found.

▼ Search Limiters

1. -2178-1988. Program analysis techniques for algorithmic complexity and relational properties.

Degree: PhD, Computer Science, 2019, University of Texas – Austin

URL: http://dx.doi.org/10.26153/tsw/2181

Analyzing standard safety properties of a given program has traditionally been the primary focus of the program analysis community. Unfortunately, there are still many interesting analysis tasks that cannot be effectively expressed with standard safety properties. One such example is to derive the asymptotic complexity of a given program. Another example is to verify relational properties, i.e. properties that must be satisfied jointly by multiple programs of multiple runs of one program. Existing program analysis techniques for standard safety properties are usually not immediately applicable to asymptotic complexity analysis problems and relational verification problems. New approaches are therefore needed to solve these unconventional problems. This thesis studies techniques for algorithmic complexity analysis as well as relational verification. To that end, we present three case studies: (1) We propose a new fuzzing technique for automatically finding inputs that trigger a program's worst-case resource usage. (2) We show how to build a scalable, end-to-end side channel detection tool by combining static taint analysis and a program logic designed for verifying non-interference of a given program. (3) We propose a general and effective relational verification algorithm that combines reinforcement learning with backtracking search. A common theme among all these solutions is to exploit problem-specific structures and adapt existing techniques to exploit those structures accordingly. Advisors/Committee Members: Dillig, Isil (advisor), Lin, Calvin (committee member), Chidambaram, Vijay (committee member), Tiwari, Mohit (committee member).

Subjects/Keywords: Complexity testing; Optimal program synthesis; Fuzzing; Genetic programming; Performance bug; Vulnerability detection; Side channel; Static analysis; Relational verification; Reinforcement learning; Policy gradient

10 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

-2178-1988. (2019). Program analysis techniques for algorithmic complexity and relational properties. (Doctoral Dissertation). University of Texas – Austin. Retrieved from http://dx.doi.org/10.26153/tsw/2181