Algebraic formal methods for invariant generation

Orientador: Arnaldo Vieira MouraTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: É bem sabido que a automação e a eficácia de métodos de verificação formal de softwares, sistemas embarcados ou sistemas híbridos, depende da facilidade com que invariantes precisas possam ser geradas automaticamente a partir do código fonte. Uma invariante é uma propriedade, especificada sobre um local específico do código fonte, e que sempre se verifica a cada execução de um sistema. Apesar dos progressos enormes ao longo dos anos, o problema da geração de invariantes ainda está em aberto para tanto programas não-lineares discretos, como para sistemas não-lineares híbridos. Nesta tese, primeiramente, apresentamos novos métodos computacionais que podem automatizar a descoberta e o fortalecimento de relações não-lineares entre as variáveis de um programa que contém laços não-lineares, ou seja, programas que exibem relações polinomiais multivariadas e manipulações fracionarias. Além disso, a maioria dos sistemas de segurança críticos, tais como aviões, automóveis, produtos químicos, usinas de energia e sistemas biológicos, operam semanticamente como sistemas híbridos não-lineares. Nesse trabalho, apresentamos poderosos métodos computacionais que são capazes de gerar bases de ideais polinomiais de invariantes não-lineares para sistemas híbridos não-lineares. Em segundo lugar, apresentamos métodos pioneiros de verificação que automaticamente gerem bases de invariantes expressas por séries de potências multi-variáveis e por funções transcendentais. Discutimos, também, a sua convergência em sistemas híbridos que exibem modelos não lineares. Verificamos que as séries de potência geradas para invariantes são, muitas vezes, compostas pela expansão de algumas funções transcendentais bem conhecidas, tais como "log" e "exp". Assim, apresentam uma forma analisável fechada que facilita o uso de invariantes na verificação de propriedades de segurança. Para cada problema de geração de invariantes estabelecemos condições suficientes, muito gerais, que garantem a existência e permitem o cálculo dos ideais polinomiais para situações que não podem ser tratadas pelas abordagens de geração invariantes hoje conhecidas. Finalmente, estendemos o domínio de aplicações, acessíveis através de métodos de geração de invariantes, para a área de segurança. Mais precisamente, fornecemos uma plataforma extensível baseada em invariantes pré-computadas que seriam usadas como assinaturas semânticas para análise de intrusos ("malwares") e deteção dos ataques de intrusões mais virulentos. Seguindo a concepção de tais plataformas, propomos sistemas de detecção de intrusão, usando modelos gerados automaticamente, onde as chamadas de sistema e de funções são vigiados pela avaliação de invariantes, pré-calculadas para denunciar qualquer desvio observado durante a execução da aplicação. De modo abrangente, nesta tese, propomos a redução de problemas de geração de invariantes para problemas algébricos lineares. Ao reduzir os problemas de geração de invariante não-triviais de sistemas híbridos não-lineares para problemas algébricos lineares relacionados, somos capazes de ultrapassar as deficiências dos mais modernos métodos de geração de invariante hoje conhecidos permitindo, assim, a geração automática e eficiente de invariantes para programas e sistemas híbridos não lineares complexos. Tais métodos algébricos lineares apresentam complexidades computacionais significativamente inferiores àquelas exigidas pelos os fundamentos matemáticos das abordagens usadas hoje, tais como a computação de bases de Gröbner, a eliminação de quantificadores e decomposições cilíndricas algébricasAbstract: It is well-known that the automation and effectiveness of formal software verification of embedded or hybrid systems depends to the ease with which precise invariants can be automatically generated from source specifications. An invariant is a property that holds true at a specific location in the specification code, whenever an execution reaches that location. Despite tremendous progress over the years, the problem of invariant generation remains very challenging for both non-linear discrete programs, as well as for non-linear hybrid systems. In this thesis, we first present new computational methods that can automate the discovery and can strengthen interrelationships among the variables of a program that contains non-linear loops, that is, programs that display multivariate polynomial and fractional manipulations. Moreover, most of safety-critical systems such as aircraft, cars, chemicals, power plants and biological systems operate semantically as non-linear hybrid systems. In this work, we demonstrate powerful computational methods that can generate basis for non-linear invariant ideals of non-linear hybrid systems. Secondly, we present the first verification methods that automatically generate basis for invariants expressed by multivariate formal power series and transcendental functions. We also discuss their convergence over hybrid systems that exhibit non linear models. The formal power series invariants generated are often composed by the expansion of some well-known transcendental functions e.g. log and exp. They also have an analysable closed-form which facilitates the use of the invariants when verifying safety properties. For each invariant generation problem, we establish very general sufficient conditions that guarantee the existence and allow for the computation of invariant ideals for situations that can not be treated in the presently known invariant generation approaches. Finally, we extend the domain of applications for invariant generation methods to encompass security problems. More precisely, we provide an extensible invariant-based platform for malware analysis and show how we can detect the most virulent intrusions attacks using these invariants. We propose to automatically generate invariants directly from the specified malware code in order to use them as semantic aware signatures, i.e. malware invariant, that would remain unchanged by most obfuscated techniques. Folix lowing the design of such platforms, we propose host-based intrusion detection systems, using automatically generated models where system calls are guarded by pre-computed invariants in order to report any deviation observed during the execution of the application. In a broad sense, in this thesis, we propose to reduce the verification problem of invariant generation to algebraic problems. By reducing the problems of non-trivial nonlinear invariant generation for programs and hybrid systems to related linear algebraic problems we are able to address various deficiencies of other state-of-the-art invariant generation methods, including the efficient treatment of complicated non-linear loop programs and non-linear hybrid systems. Such linear algebraic methods have much lower computational complexities than the mathematical foundations of previous approaches know today, which use techniques such as as Gröbner basis computation, quantifier elimination and cylindrical algebraic decompositionDoutoradoCiência da ComputaçãoDoutor em Ciência da Computaçã