Software systems are ubiquitous in today's world and yet, remain vulnerable to the fallibility of human programmers as well as the unpredictability of their operating environments. The overarching goal of this dissertation is to develop algorithms to enable automated and efficient design and analysis of reliable programs. In the first and second parts of this dissertation, we focus on the development of programs that are free from programming errors. The intent is not to eliminate the human programmer, but instead to complement his or her expertise, with sound and efficient computational techniques, when possible. To this end, we make contributions in two specific domains. Program debugging --- the process of fault localization and error elimination from a program found to be incorrect --- typically relies on expert human intuition and experience, and is often a lengthy, expensive part of the program development cycle. In the first part of the dissertation, we target automated debugging of sequential programs. A broad and informal statement of the (automated) program debugging problem is to suitably modify an erroneous program, say P, to obtain a correct program, say P'. This problem is undecidable in general; it is hard to formalize; moreover, it is particularly challenging to assimilate and mechanize the customized, expert programmer intuition involved in the choices made in manual program debugging. Our first contribution in this domain is a methodical formalization of the program debugging problem, that enables automation, while incorporating expert programmer intuition and intent. Our second contribution is a solution framework that can debug infinite-state, imperative, sequential programs written in higher-level programming languages such as C. Boolean programs, which are smaller, finite-state abstractions of infinite-state or large, finite-state programs, have been found to be tractable for program verification. In this dissertation, we utilize Boolean programs for program debugging. Our solution framework involves two main steps: (a) automated debugging of a Boolean program, corresponding to an erroneous program P, and (b) translation of the corrected Boolean program into a correct program P'. Shared-memory concurrent programs are notoriously difficult to write, verify and debug; this makes them excellent targets for automated program completion, in particular, for synthesis of synchronization code. Extant work in this domain has focused on either propositional temporal logic specifications with simplistic models of concurrent programs, or more refined program models with the specifications limited to just safety properties. Moreover, there has been limited effort in developing adaptable and fully-automatic synthesis frameworks that are capable of generating synchronization at different levels of abstraction and granularity. In the second part of this dissertation, we present a framework for synthesis of synchronization for shared-memory concurrent programs with respect to temporal logic specifications. In particular, given a concurrent program composed of synchronization-free processes, and a temporal logic specification describing their expected concurrent behaviour, we generate synchronized processes such that the resulting concurrent program satisfies the specification. We provide the ability to synthesize readily-implementable synchronization code based on lower-level primitives such as locks and condition variables. We enable synchronization synthesis of finite-state concurrent programs composed of processes that may have local and shared variables, may be straight-line or branching programs, may be ongoing or terminating, and may have program-initialized or user-initialized variables. We also facilitate expression of safety and liveness properties over both control and data variables by proposing an extension of propositional computation tree logic. Most program analyses, verification, debugging and synthesis methodologies target traditional correctness properties such as safety and liveness. These techniques typically do not provide a quantitative measure of the sensitivity of a computational system's behaviour to unpredictability in the operating environment. We propose that the core property of interest in reasoning in the presence of such uncertainty is robustness --- small perturbations to the operating environment do not change the system's observable behavior substantially. In well-established areas such as control theory, robustness has always been a fundamental concern; however, the techniques and results therein are not directly applicable to computational systems with large amounts of discretized, discontinuous behavior. Hence, robustness analysis of software programs used in heterogeneous settings necessitates development of new theoretical frameworks and algorithms. In the third part of this dissertation, we target robustness analysis of two important classes of discrete systems --- string transducers and networked systems of Mealy machines. For each system, we formally define robustness of the system with respect to a specific source of uncertainty. In particular, we analyze the behaviour of transducers in the presence of input perturbations, and the behaviour of networked systems in the presence of channel perturbations. Our overall approach is automata-theoretic, and necessitates the use of specialized distance-tracking automata for tracking various distance metrics between two strings. We present constructions for such automata and use them to develop decision procedures based on reducing the problem of robustness verification of our systems to the problem of checking the emptiness of certain automata. Thus, the system under consideration is robust if and only if the languages of particular automata are empty. / text

Diagnóstico baseado em modelos (Model Based Diagnosis - MBD) é uma técnica de Inteligência Artificial usada para encontrar componentes falhos em dispositivos físicos. MBD também tem sido utilizado para auxiliar programadores experientes a encontrarem falhas em seus programas, sendo essa técnica chamada de Depuração de Programas baseada em Modelos (Model Based Software Debugging - MBSD). Embora o MBSD possa auxiliar programadores experientes a entenderem e corrigirem suas falhas, essa abordagem precisa ser aprimorada para ser usada por aprendizes de programação. Esse trabalho propõe o uso da técnica de depuração hierárquica de programas, uma extensão da técnica MBSD, para que aprendizes de programação sejam capazes de depurar seus programas raciocinando sobre componentes abstratos, tais como: padrões elementares, funções e procedimentos. O depurador hierárquico de programas proposto foi integrado ao Dr. Java e avaliado com um grupo de alunos de uma disciplina de Introdução à Programação. Os resultados mostram que a maioria dos alunos foi capaz de compreender as hipóteses de falha geradas pelo depurador automático e usar essas informações para corrigirem seus programas. / Model Based Diagnosis (MBD) in Artificial Intelligence is a technique that has been used to detect faulty components in physical devices. MBD has also been used to help senior programmers to locate faults in software with a technique known as Model Based Software Debugging (MBSD). Although this approach can help experienced programmers to detect and correct faults in their programs, this approach must be improved to be used with novice programmers. This work proposes a hierarchical program diagnosis, a MBSD extension, to help novice programmers to debug programs by exploring the idea of abstract components, such as: elementary patterns, functions and procedures. The hierarchical program debugger proposed was integrated to the Dr. Java tool and evaluated with students of an introductory programming course. The results showed that most of the students were able to understand the hypotheses of failure presented by the automated debugger and use this information to provide a correction for their programs

Diagnóstico baseado em modelos (Model Based Diagnosis - MBD) é uma técnica de Inteligência Artificial usada para encontrar componentes falhos em dispositivos físicos. MBD também tem sido utilizado para auxiliar programadores experientes a encontrarem falhas em seus programas, sendo essa técnica chamada de Depuração de Programas baseada em Modelos (Model Based Software Debugging - MBSD). Embora o MBSD possa auxiliar programadores experientes a entenderem e corrigirem suas falhas, essa abordagem precisa ser aprimorada para ser usada por aprendizes de programação. Esse trabalho propõe o uso da técnica de depuração hierárquica de programas, uma extensão da técnica MBSD, para que aprendizes de programação sejam capazes de depurar seus programas raciocinando sobre componentes abstratos, tais como: padrões elementares, funções e procedimentos. O depurador hierárquico de programas proposto foi integrado ao Dr. Java e avaliado com um grupo de alunos de uma disciplina de Introdução à Programação. Os resultados mostram que a maioria dos alunos foi capaz de compreender as hipóteses de falha geradas pelo depurador automático e usar essas informações para corrigirem seus programas. / Model Based Diagnosis (MBD) in Artificial Intelligence is a technique that has been used to detect faulty components in physical devices. MBD has also been used to help senior programmers to locate faults in software with a technique known as Model Based Software Debugging (MBSD). Although this approach can help experienced programmers to detect and correct faults in their programs, this approach must be improved to be used with novice programmers. This work proposes a hierarchical program diagnosis, a MBSD extension, to help novice programmers to debug programs by exploring the idea of abstract components, such as: elementary patterns, functions and procedures. The hierarchical program debugger proposed was integrated to the Dr. Java tool and evaluated with students of an introductory programming course. The results showed that most of the students were able to understand the hypotheses of failure presented by the automated debugger and use this information to provide a correction for their programs