sábado, 5 de maio de 2018

Rely/Guarantee Refinement Calculus' blog


On my PhD, I worked on the mechanisation of a refinement calculus to supports derivation of programs specified using rely-guarantee. Yesterday, while preparing a manuscript to FACJ, I decided to start a blog about the theory that I worked on during the PhD. The blog can be accessed here.


The thesis:

My thesis is entitled Mechanising an Algebraic Rely-Guarantee Refinement Calculus. Refinement calculus can be thought as programming methodologies where design decisions are formally recorded. They generally consist on a collection of refactoring templates that can be applied by a programmer to transform mathematical specifications into executable code. The benefit of using this approach is that it guarantees that the implementation constructed by the programmer does exactly what the mathematical specification demands. This methodology results in software that is correct-by-construction, eliminating potential costs in post-production due to bugs. In my thesis this approach is illustrated via the derivation of non-trivial algorithms taken from the literature on refinement calculus.

quarta-feira, 25 de outubro de 2017

Exemplos de especificacoes em Z


Em resposta a um visitante do blog, estou adicionando um exemplo de especificacoes em Z que usei durante minha experiencia com Z/Eves.

1. IBM CIC'S Browser Component


Este mecanização corresponde ao exemplo discutido no post



Abraco,
Diego Dias

terça-feira, 3 de outubro de 2017

Technical Report No 257 by IBM (A specification, refinement and Verification Using Z Schema Calculus)



The document made available on this post was recovered during the moving from Claremont Tower to the Urban Sciences Building while I was at Newcastle University. Leo Freitas, one of the co-authors of the paper "Mecanizando o componente de navegação do IBM’s CICS: um experimento do Grande Desafio" found a paper copy of this document and gave. It was part of my first foray into the mechanisation of formal theories using theorem provers, and since it is the basis for the paper mentioned above, and it is unrestricted, I decided to make it available!

A specification, refinement and Verification Using Z Schema Calculus

Enjoy it!

sexta-feira, 7 de junho de 2013

Contact Details / About myself


Nowadays I'm a first-year PhD student in Computer Science at Newcastle University. Previously, I did a MSc at the Federal University of Pernambuco (UFPE, 2012 - Brazil) under supervision of Juliano Iyoda, and a BSc in Computer Science at the Federal University of Bahia (UFBA, 2010 - Brazil) with conclusion work under supervision of Adolfo Duran and Aline Andrade. You can find and download some the papers I published through links on my Research Gate's profile.  More details about me are available at my profissional profile in Linkedin.

My master's dissertation title is Behavioural Preservation in Fault Tolerant Patterns and can be download from here. In order to read just the abstract, see this post. During the masters I published part of the disseration on the 14th Brazilian Symposium on Formal Methods (link). An extended version of this paper is under revision for publication in the Science of Computer Programming Journal.

My BSc's dissertation is entitled Formal Verification of the Scheduler and Synchronous Message System of a Simple Kernel (original title: Verificação formal do escalonador e do sistema de troca de mensagens síncronas de um simple kernel) and is only available in portuguese. You can download the text from this link.

In order to contact me you can post a comment in this blog. By doing it I will receive an email with your post and make effort to answer your post as soon as possible. I've regarded to translate this blog to english, as a great number of visitors are from countries where english is spoken, however I haven't had time to do it so far.



terça-feira, 4 de junho de 2013

Behavioural Preservation in Fault Tolerant Patterns


 

Behavioural Preservation in Fault Tolerant Patterns

 

Abstract

In the development of critical systems it is common practise to make use of redundancy in order to achieve higher levels of reliability. There are well established design patterns that introduce redundancy and that are widely documented in the literature and adopted by the industry. However there have been few attempts to formally verify them with respect to behavioural preservation.

In this work, we purpose an approach to specify such design patterns, called here
fault tolerant patterns, using HOL. We use the theorem prover HOL4 to prove the compositionality and correctness of the fault tolerant patterns. We illustrate our approach by modelling three classical fault tolerant patterns: homogeneous redundancy, heterogeneous redundancy and triple modular redundancy. Our model takes into account that the original system (without redundancy) computes a certain function with some delay and is amenable to random failures.

In order to prove that a fault tolerant pattern preserves the behaviour of its subsystems, we defined new notions of refinement. Systems engineers commonly accept the fact that fault tolerant patterns do not change the functionality of a system. However, this practise is not compatible with the classical refinement notions. Thus we defined axiomatic notions of refinement to prove that the formalised fault tolerant patterns preserve the behaviour of its subsystems.

We also proved that our fault tolerant patterns are compositional in the sense that we can apply fault tolerant patterns consecutively and for an arbitrary number of times. The result of that is still a system whose delay, failure model and functionality can be systematically discovered (by proof) with almost no effort.

In order to illustrate the usage of the patterns we applied the triple modular redundancy pattern to a simplified avionic Elevator Control System. We showed that once a fault tolerant pattern is verified, the application of it to a specific system and the proof of the behavioural preservation of the resulting system becomes trivial. This work has been done in collaboration with the Brazilian aircraft manufacturer Embraer.


Keywords:
Fault tolerance patterns, HOL4, behavioural preservation, refinement.Download [PDF].

quarta-feira, 15 de setembro de 2010

Papers de trabalhos com Z/Eves

Alguns artigos de projetos desenvolvidos com Z/Eves estão disponíveis em:
ftp://ftp.cs.york.ac.uk/pub/leo/papers/

Procurando no google dá pra encontrar as dissertações de mestrado citadas nos artigos.


Nota:
Estes artigos não são um bom ponto de partida para entender Z nem Z/Eves, mas são úteis em descrever como superar problemas com provas em Z/Eves e como medir o esforço empregado na mecanização de especificações. Como ponto de partida para mexer com Z/Eves, o Z/Eves User's Guide é essencial.

Especificação do Browse Component em Z/Eves

Estou adicionando a especificação do CICS, descrita no artigo:
Mecanizando o componente de navegação do IBMs CICS: um experimento do Grande Desafio.


"Mechanising IBM's CICS Browser Component: An experiment of the Grand Challenge" in ERBASE 2009. Original title: Mecanizando o componente de navegação do IBMs CICS: um experimento do Grande Desafio.

Documento original: ftp://ftp.cs.york.ac.uk/pub/leo/mefes/cics/z-refinement/
Article/Artigo: https://dl.dropboxusercontent.com/u/11299884/Papers/erbase-09.pdf
Specification/Especificação: http://dl.dropbox.com/u/11299884/ZEves/Specification.zip

Mini-curso Z/Eves - Erbase 2010

Estou adicionando o material do mini-curso que ocorreu no inicio desta ano
na ERBASE 2010 (Escola Regional de Computação - Bahia, Alagoas, Sergipe)
em Maceió-AL.


Os slides do mini-curso realizado na ERBASE 2010 encontram-se em:
http://dl.dropbox.com/u/11299884/Minicurso/Minicurso.pdf

Os arquivos do experimento usado no mini-curso estão em:
http://dl.dropbox.com/u/11299884/Minicurso/spec-filesystem-erbase2010.zip

Monografia: Introdução ao Z/Eves

Minha monografia contem uma secao sobre Z/Eves no capitulo 2. Abaixo segue o link para download:

https://www.dropbox.com/s/hrswduk5dyp18po/MonografiaAdaptada.pdf?dl=0



sábado, 14 de novembro de 2009

Forma normal Prenex

Olá, uma dica para quem tiver interesse em saber mais sobre a forma normal prenex, usada pelo Z/Eves para remover quantificadores de uma expressão:

http://pt.wikipedia.org/wiki/Forma_normal_prenex

Cálculo de precondição de operações compostas

Conjectura experimental:

Dada uma operação OP sobre o estado STATE, que é formada pela disjunção das operações OP1, OP2, ..., OPn, cujas precodições OP1Sig, OP2Sig, ..., OPnSig são calculadas através dos teoremas tOP1, tOP2, ..., tOPn, é possível calcular a precondição da operação OP utilizando o algoritmo:

ENTRADA DO ALGORITMO:

1. Schemas que encapsulam precondições: OP1Sig, ..., OPnSig.
2. Schema que encapsula precondição da operação OP, isto é:
OPSig \defs OP1Sig \lor OP2Sig \lor ... OPnSig
3. Teoremas de precondições tOP1, tOP2, .., tOPn


ALGORITMO:

Build-Z/Eves-Proof-Script {
let i = 1
while (i<=n) {
split
OPiSig
invoke OPiSig
cases
use tOPi with disabled (OP1, OP2, ..., OPn, STATE) prove by reduce
for EACH-COMPONENT existentially quantified in current goal do:
instantiate (COMPONENT1__0'==COMPONENT1',
COMPONENT2__0'==COMPONENT2', ...,
COMPONENTn__0'==COMPONENTn')

rewrite
next

let i = i+1
}
invoke rewrite
next
}


Prova de conceito: ToyGenericProofDesing.zip



Este tópico está aberto a discussões, dado que é um resultado experimental e sem prova. Este reasoning sobre provas foi extraído do arquivo de prova da verificação do Simple Kernel. Para estudantes do MEFES que tenham acesso aos arquivos de prova do simple kernel, podem verificar a aplicação deste reasoning na prova da precondição da operação EnqueuePRIOQ.


Nota: o formato usado para calcular a precondição das operações OP1, ..., OPn utilizado neste algoritmo, baseia-se em escrever a assinatura do teorema de precondição utilizando Schemas. Este raciocínio é explicado no artigo "Mecanizando o componente de navegação do IBM CICS: um experimento do Grande Desafio".

quinta-feira, 5 de novembro de 2009

Challenge: Proof Loops !

Olá,

Estou com uma dúvida sobre o mecanismo de funcionamento do Z/EVES e irei de compartilhá-la com vocês. O problema que irei descrever ocorre quando existem duas regras de reescrita, tal que o que a primeira regra reescreve A por B, e a segunda regra reescreve B por A. Eu esperava que o provador entrasse em loop caso eu deixasse as duas regras abilitadas e tentasse provar um outro teorema que tivesse o predicado A.

Por que eu esperava isso?

Porque o provador iria usar a regra 1 para reescrever A por B; depois usar a regra 2 para reescrever B por A; depois usar a regra 1 para reescrever A por B; e assim por diante (infinitamente).

Consegui simular esta situação no Z/EVES em dois arquivos de prova. No primeiro, o provador não entra em loop; no segundo, o provador entra em loop. Minha dúvida é: por que, no primeiro caso, o provador não entra em loop?

PRIMEIRO ARQUIVO: NoProofLoops.tex

% A regra de reescrita rUnflex reescreve x \subseteq y por x \in \power y

\begin{theorem}{rule rUnflex}
\forall x, y: \power \num @ x \subseteq y \iff x \in \power y
\end{theorem}

% A regra de reescrita rUnflex2 reescreve x \in \power y por x \subseteq y

\begin{theorem}{rule rUnflex2}
\forall x, y: \power \num @ x \in \power y \iff x \subseteq y
\end{theorem}

% O teorema Test possui o padrão que permitirá a regra de
% reescrita rUnflex ser ativada.
\begin{theorem}{Test}
\forall x, y: \power \num | x \subseteq y @ x = y
\end{theorem}

SEGUNDO ARQUIVO: ProofLoops.tex

\begin{theorem}{rule rUnflex}
\forall x, y: \power \num @ x \subseteq y \iff x \in \power y
\end{theorem}

\begin{theorem}{rule rUnflex2}
\forall x, y: \power \num @ x \in \power y \iff (\exists w: \power \num | w = y @ x\subseteq w)
\end{theorem}

\begin{theorem}{Test}
\forall x, y: \power \num | x \subseteq y @ x = y
\end{theorem}


LOOP: Tente provar Test usando rewrite


Minha suposição é que o provador guarda três estados: BeforeLastRewriteRule, AfterLastRewriteRule, AfterThisRewriteRule.

IF (AfterThisRewriteRule = BeforeLastRewriteRule) THEN
NotApplyThisRule
ELSE
ApllyThisRule


Se alguém aqui já trabalhou com implementação de um provador de teoremas, ou conhece alguém que já, serei muito grato se procurar saber o real mecanismo usados para evitar proof loops e descrever este mecanismo para os leitores do blog.

sexta-feira, 17 de julho de 2009

Teoremas de equivalência

Sejam P e Q schemas equivalentes. Para mostrar a equivalência entre estes schemas usando Z/Eves deve ser provado o predicado:

P \iff Q

Uma forma tipica de mostrar esta equivalência é dividi-la em duas partes:

1. P \implies Q
2. Q \implies P

Para transformar o predicado P \iff Q nos predicados 1 e 2, o usuário pode entrar com os seguintes comandos de prova:

slip P
rewrite
cases
rewrite

Neste ponto o predicado 1 foi obtido.

next
split Q
rewrite

Neste ponto o predicado 2 foi obtido.

Agora, é somente provar os predicados. Para alternar entre eles utiliza-se o comando next.

Mecanizando o componente de navegação do IBMs CICS

O site do MEFES (Métodos Formais em Engenharia de Software) está hospedado em https://wiki.dcc.ufba.br/MEFES/. Neste endereço está disponível para download o artigo "Mecanizando o componente de navegação do IBMs CICS: um experimento do Grande Desafio". O artigo foi publicado na IX ERBASE e foi premiado com o terceiro lugar no Workshop de Trabalhos de Iniciação Científica e de Graduação (WTICG). A ERBASE é um evento regional promovido anualmente pela Sociedade Brasileira de Computação.

Como citar:

DIAS, D. M. ; Robson Silva ; Leo Freitas ; Adolfo Duran . Mecanizando o componente de navegação do IBMs CICS: um experimento do Grande Desafio. In: IX Escola Regional de Computação Bahia - Alagoas - Sergipe, 2009, Ilheus. Anais da IX ERBASE, 2009.

quarta-feira, 19 de novembro de 2008

Comando: Rewrite

1. Usa equality substitute (ex: PreMakeReceiver)

Comando: Reduce


1. Usa invoke
2. Usa frule
3. Usa grule
4. Usa rules



Comando: Trivial rewrite

1. Usa regra de reescrita
2. Não faz reason aritmético
3. Não usa grules
4. Não faz simplificação
5. Talvez não use regra de reescrita com Generic actuals

Comando: Simplify

1. Não usa regra de reescrita.
2. Usa foward rules.
3. Usa grule
4. Faz reason aritmético
Ex: identidades
5. Não infere: A \in \power A
6. Faz simplificações lógicas
Ex: (PREDICATE \iff true) é substituído por (PREDICATE)

domingo, 26 de outubro de 2008

Comando: Instantiate

Parte I - Uso do instante para eliminar quantificador existencial da conclusão.

Problema:

As vezes, para concluir uma prova (teorema da inicialização, por exemplo), pode ser necessário resolver um problema com o formato:

[set of premiss \implies] \exist variable : TYPE @ predicate

Nesta situação, o quantificador existencial precisa ser eliminado. Para realizar isto, o especificador precisa encontrar uma witness para eliminar o quantificador existencial utilizando o comando instantiate. Em alguns casos, é necessário definir a witness para depois poder utilizá-la. Na notação acima, o que está entre colchetes é opcional.


Uma vez em posse da witness, utiliza-se o comando instantiate para instrui o provador a aplicar a one-point-rule e transformar o predicado para o predicado.

[set of premiss \implies] witness \in TYPE \land predicate[witness/variable]
\lor \exist variable : TYPE @predicate


O segundo passo da transformação é mostrado a seguir e é aplicado se a parte opcional destaca entre colchetes estiver presente no predicado.

set of premiss \land (\not (witness \in TYPE \land predicate[witness/predicate])) \implies \exist variable @predicate



Seja C um predicado contendo um quantificador existencial. Seja A um conjunto de premissas. Então, o resultado de um comando de instanciação da variável declarada em C resulta nos seguintes passos de prova:

1. A => C
2. A => B or C
3. A and NOT(B) => C

Do passo 1 para o 2 é aplicado a One-Point-Rule:





Do passo 2 para o passo 3 é aplicado transformação lógica.





quarta-feira, 22 de outubro de 2008

Usando Grules

O uso de grules aumenta significativamente o grau de automação de uma prova, pois em situações específicias elimina a necessidade do especificador lidar com problemas referentes a tipos e restrições de valores durante a prova de teoremas (Domain Check e Preconditions por exemplo). Abaixo descrevo como inserir uma grule no Sistema Policial e depois apresento um conjunto de exemplos de situações em que grules podem ser utilizadas.

A quarta versão do Sistema Policial não adiciona nenhuma mudança substancial. Apenas foi adicionado na prova uma regra de automação do tipo grule. O teorema

\begin{theorem}{grule gCPFMaxType}
CPF \in \power \num
\end{theorem}

é usado para dizer ao Z/Eves qual tipo maximal de CPF, sem que seja necessário realizar a expansão de CPF. Isto é, se durante a prova de alguma operação o Z/Eves produzir como objetivo de prova o predicado:

CPF \in \power \num

Então este predicado será convertido a true sem que seja necessário invocar a definição de CPF.

O Z/Eves gera grules quando são definidas constantes em axiomatic-box e generic-box como pode ser observado no Reference Manual 1.5, pag. 20. Free types e schemas também geram grules (descobri isto mexendo). Para mais informações sobre grule consulte o Z/Eves User's Guide 2.3, pag. 41. Um link para um arquivo contendo um conjunto de exemplos ilustrando o uso de grules no Z/Eves está disponível no final da página. Abaixo, discuto estes exemplos.

Grules_Example01 - São definidos dois tipos. É apresentado um teorema em que o predicado envolve o tipo maximal dos tipos defindos antes. Note que para provar este teorema o especificador precisa instruir o Z/Eves manualmente (realizando expansão - i.e., Invoke).

Grules_Example02 - O mesmo exemplo anterior, só que agora foi criada uma grule para informar ao Z/Eves o tipo maximal de B. Para provar o teorema sobre o tipo de B não é necessário expandir B.

Voce deveria notar nos dois exemplos anteriores que o Z/Eves não criou nenhum teorema para os tipos inseridos pelo usuário. Foram inseridos given sets e abbreviations. Nestas situações o especificador deve se encarregar de criar grules para os tipos, se houver necessidade.

Grules_Example03 - Um exemplo maior, utilizando given sets e schemas. Note que quando um schema é definido e é utilizado como tipo, o Z/Eves gera automaticamente a grule SchemaName$declaration. Note também que, se um schema é definido e não é utilizado como tipo, o Z/Eves não gera a regra de automação do tipo grule para o schema. Neste exemplo, o tipo C não foi utilizado como tipo e por isso o Z/Eves não gerou uma grule associada a TIPO_C.

Grules_Example04 - O exemplo anterior, com uma grule adicionada para TIPO_C. A grule não está provada. Não consegui realizar a prova desta grule. Se conseguir, envie-me a resolução. Thanks ;-)

Grules_Example05 - Neste exemplo uma grule é utilizada para adicionar informação sobre restrição de valor. Para isto, dois valores, minvalue e maxvalue, foram definidos através de um axiomatic-box. Ainda no axiomatic-box há uma rule relacionando os dois valores através do predicado: minvalue \leq maxvalue

No teorema ListInitialisation um dos goals é mostrar que: 0 \leq minvalue. A grule foi utilizada para evitar que o especificador tivesse que lidar com a expansão de \nat ao realizar a prova de ListInitialisation.

Este teorema foi propositalmente posto em dois lugares, antes e depois da grule. Pretendeu-se assim mostrar o ganho de automação com o uso da grule.

Note que este exemplo difere bastante dos anteriores, pois usou grules para adicionar informação sobre uma restrição de valor e não sobre tipos.


A quarta versão do sistema policial está disponível em: http://www.dcc.ufba.br/~diego052/experimento/zevesblog/SistemaPolicial_v4.zip


O arquivo de exemplos de uso de grules está disponível em: http://www.dcc.ufba.br/~diego052/experimento/zevesblog/Grules_Examples_01-05.zip