subject:(Optimal program synthesis) – OATD

Open Access Theses and Dissertations

Advanced search options

Advanced Search Options ^🞨

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

Find ETDs with:

		in
And / Or
		in
And / Or
		in
And / Or
		in

Written in Published in Earliest date Latest date

Sorted by

Only ETDs with Creative Commons licenses

Results per page:

Sorted by: relevance · author · university · date | New search

You searched for subject:(Optimal program synthesis). Showing records 1 – 2 of 2 total matches.

▼ 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

Sample image

Sample image

Sample image

Sample image

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

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

Chicago Manual of Style (16^th Edition):

-2178-1988. “Program analysis techniques for algorithmic complexity and relational properties.” 2019. Doctoral Dissertation, University of Texas – Austin. Accessed March 01, 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 (7^th Edition):

-2178-1988. “Program analysis techniques for algorithmic complexity and relational properties.” 2019. Web. 01 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 01]. 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

Pontifical Catholic University of Rio de Janeiro

2. DOUGLAS MOTA DIAS. [en] AUTOMATIC SYNTHESIS OF DIGITAL MICROCONTROLLER PROGRAMS BY GENETIC PROGRAMMING.

Degree: 2005, Pontifical Catholic University of Rio de Janeiro

URL: http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6666

[pt] Esta dissertação investiga o uso de programação genética linear na síntese automática de programas em linguagem de montagem para microcontroladores, que implementem estratégias de controle de tempo ótimo ou sub-ótimo, do sistema a ser controlado, a partir da modelagem matemática por equações dinâmicas. Uma das dificuldades encontradas no projeto convencional de um sistema de controle ótimo é que soluções para este tipo de problema normalmente implicam em uma função altamente não-linear das variáveis de estado do sistema. Como resultado, várias vezes não é possível encontrar uma solução matemática exata. Já na implementação, surge a dificuldade de se ter que programar manualmente o microcontrolador para executar o controle desejado. O objetivo deste trabalho foi, portanto, contornar tais dificuldades através de uma metodologia que, a partir da modelagem matemática de uma planta, fornece como resultado um programa em linguagem de montagem. O trabalho consistiu no estudo sobre os possíveis tipos de representações para a manipulação genética de programas em linguagem de montagem, tendo sido concluído que a linear é a mais adequada, e na implementação de uma ferramenta para realizar os três estudos de caso: water bath, cart centering e pêndulo invertido. O desempenho de controle dos programas sintetizados foi comparado com o dos sistemas obtidos por outros métodos (redes neurais, lógica fuzzy, sistemas neurofuzzy e programação genética). Os programas sintetizados demonstraram, no mínimo, o mesmo desempenho, mas com a vantagem adicional de fornecerem a solução já no formato final da plataforma de implementação escolhida: um microcontrolador.

[en] This dissertation investigates the use of genetic programming in automatic synthesis of assembly language programs for microcontrollers, which implement time-optimal or sub-optimal control strategies of the system to be controlled, from the mathematical modeling by dynamic equations. One of the issues faced in conventional design of an optimal control system is that solutions for this kind of problem commonly involve a highly nonlinear function of the state variables of the system. As a result, frequently it is not possible to find an exact mathematical solution. On the implementation side, the difficulty comes when one has to manually program the microcontroller to run the desired control. Thus, the objective of this work was to overcome these difficulties applying a methodology that, starting from the mathematical modeling of a plant, provides as result an assembly language microcontroller program. The work included a study of the possible types of genetic representation for the manipulation of assembly language programs. In this regard, it has been concluded that the linear is the most suitable representation. The work also included the implementation of a tool to accomplish three study cases: water bath, cart centering and inverted pendulum. The performance of control of the synthesized programs was compared with the one obtained by other methods (neural networks,…

Advisors/Committee Members: MARCO AURÉLIO CAVALCANTI PACHECO.

Subjects/Keywords: [pt] CONTROLE OTIMO; [en] OPTIMAL CONTROL; [pt] SINTESE DE PROGRAMAS; [en] PROGRAM SYNTHESIS; [pt] PROGRAMACAO GENETICA; [en] GENETIC PROGRAMMING; [pt] LINGUAGEM DE MONTAGEM; [en] ASSEMBLY LANGUAGE; [pt] MICROCONTROLADOR; [en] MICROCONTROLLER

Record Details Similar Records Cite « Share

❌

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

APA (6^th Edition):

DIAS, D. M. (2005). [en] AUTOMATIC SYNTHESIS OF DIGITAL MICROCONTROLLER PROGRAMS BY GENETIC PROGRAMMING. (Thesis). Pontifical Catholic University of Rio de Janeiro. Retrieved from http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6666

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

DIAS, DOUGLAS MOTA. “[en] AUTOMATIC SYNTHESIS OF DIGITAL MICROCONTROLLER PROGRAMS BY GENETIC PROGRAMMING.” 2005. Thesis, Pontifical Catholic University of Rio de Janeiro. Accessed March 01, 2021. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6666.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

DIAS, DOUGLAS MOTA. “[en] AUTOMATIC SYNTHESIS OF DIGITAL MICROCONTROLLER PROGRAMS BY GENETIC PROGRAMMING.” 2005. Web. 01 Mar 2021.

Vancouver:

DIAS DM. [en] AUTOMATIC SYNTHESIS OF DIGITAL MICROCONTROLLER PROGRAMS BY GENETIC PROGRAMMING. [Internet] [Thesis]. Pontifical Catholic University of Rio de Janeiro; 2005. [cited 2021 Mar 01]. Available from: http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6666.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

DIAS DM. [en] AUTOMATIC SYNTHESIS OF DIGITAL MICROCONTROLLER PROGRAMS BY GENETIC PROGRAMMING. [Thesis]. Pontifical Catholic University of Rio de Janeiro; 2005. Available from: http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6666

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation