Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université Laval

$25,500.00

Kleene algebra and its application to control theory and computer security

EF 2011-12

Résumé
Computers have become extremely important in many respects. They have a vital role when controlling complex systems, such as airplanes or medical apparatus. Fast computers linked to Internet let people and companies access a gigantic amount of information and make commercial transactions. The success of computers is indeed spectacular. The increased dependence on computers means that the flow of information must be precisely controlled; for instance, personal data should not be sent on the Internet without the owner's consent. Unfortunately, many programs have security flaws. These can be simple bugs that lead to undesired behaviour or bad features that are exploited by malevolent people. The goal of this research is to develop scientific techniques, based on strong mathematical foundations, to reduce the occurrence of such problems. The mathematical foundations consist mainly of the theory of control of discrete event systems (computer systems are a particular case of such systems) and of an algebraic theory known as Kleene algebra. The basic idea is to compare a mathematical description of a program to a security policy (the comparison is made by another program, not by hand). If necessary, the program is modified to make it secure (it is thus ""controlled""). This modification is calculated by using principles of control theory. But control theory cannot be used as is, becaused it was not designed to solve this type of problem. Hence, part of the research will consist in extending control theory to handle the modification of unsafe programs in order to control them. Kleene algebra will be used for the description and extension of control theory, because it leads to compact and easily verifiable proofs. Kleene algebra is presently enjoying much attention from many researchers and it is finding more and more applications in computer science, while at the same time being studied for its own sake. This research will also contribute to the development of Kleene algebra itself and in particular to an extension called Kleene algebra with domain.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
89769-2007
Name nom
Desharnais, Jules
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2007
Award amount
25500
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2706
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Software engineering
Research subject fr
Génie logiciel
Partie
5
Nb partie
5
Application title
Kleene algebra and its application to control theory and computer security
Keyword
NSERC
Application summary
Computers have become extremely important in many respects. They have a vital role when controlling complex systems, such as airplanes or medical apparatus. Fast computers linked to Internet let people and companies access a gigantic amount of information and make commercial transactions. The success of computers is indeed spectacular. The increased dependence on computers means that the flow of information must be precisely controlled; for instance, personal data should not be sent on the Internet without the owner's consent. Unfortunately, many programs have security flaws. These can be simple bugs that lead to undesired behaviour or bad features that are exploited by malevolent people. The goal of this research is to develop scientific techniques, based on strong mathematical foundations, to reduce the occurrence of such problems. The mathematical foundations consist mainly of the theory of control of discrete event systems (computer systems are a particular case of such systems) and of an algebraic theory known as Kleene algebra. The basic idea is to compare a mathematical description of a program to a security policy (the comparison is made by another program, not by hand). If necessary, the program is modified to make it secure (it is thus ""controlled""). This modification is calculated by using principles of control theory. But control theory cannot be used as is, becaused it was not designed to solve this type of problem. Hence, part of the research will consist in extending control theory to handle the modification of unsafe programs in order to control them. Kleene algebra will be used for the description and extension of control theory, because it leads to compact and easily verifiable proofs. Kleene algebra is presently enjoying much attention from many researchers and it is finding more and more applications in computer science, while at the same time being studied for its own sake. This research will also contribute to the development of Kleene algebra itself and in particular to an extension called Kleene algebra with domain.