Open Access Theses and Dissertations

Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Dates: Last 2 Years ❌

You searched for subject:(Performance bug). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ 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

Page 1 Page 2 Page 3 Page 4 Sample image Sample image Sample image Sample image
10 more images…

Record Details  Similar Records    Google PlusoneFacebookTwitterCiteULikeMendeleyreddit

❌

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

APA (6th 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

Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete

Chicago Manual of Style (16th Edition):

-2178-1988. “Program analysis techniques for algorithmic complexity and relational properties.” 2019. Doctoral Dissertation, University of Texas – Austin. Accessed March 06, 2021. http://dx.doi.org/10.26153/tsw/2181.

Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete

MLA Handbook (7th Edition):

-2178-1988. “Program analysis techniques for algorithmic complexity and relational properties.” 2019. Web. 06 Mar 2021.

Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete

Vancouver:

-2178-1988. Program analysis techniques for algorithmic complexity and relational properties. [Internet] [Doctoral dissertation]. University of Texas – Austin; 2019. [cited 2021 Mar 06]. Available from: http://dx.doi.org/10.26153/tsw/2181.

Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete

Council of Science Editors:

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

Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete

.