Using mathematics to hunt for computer errors
Security gap in application discovered, update urgently recommended. Alerts like that can confront us every week. Often, a comprehensive update that addresses teething troubles is already offered when a new programme is launched. This creates manifold problems, and public entities as well as businesses are often exposed to attacks by hackers. Software is used in a growing number of sensitive areas where a computer failure might even be life threatening. It has to be noted that not all fields are affected in the same way, many computer systems run as unfailingly as the proverbial Swiss clockwork. While hardware is usually very reliable, it is the software component that may create problems.
Mathematics improve computer systems
Complex programmes actually make it very difficult to foresee every eventuality. While computer methods for testing software exist, the complexity of applications has been steadily increasing in recent years. The performance of test methods lags behind, particularly in terms of their speed – a good incentive to invest in basic research in this field. In a recently completed project funded by the Austrian Science Fund FWF, the computer scientist Krishnendu Chatterjee analysed computer systems with the help of mathematical methods with hope of providing significant improvements in this sector.
"This field has a long-standing tradition", says Chatterjee. "Researchers have long been trying to find a formal basis for designing correct systems. Fundamental developments in this area go back to the 1960s, like the work by Alonzo Church, one of the founding fathers of computer sciences." For the mathematical analysis of computer systems, scientists use what is called 'graph theory', which deals with objects that can be characterised as networks of interconnected points or vertices. Computer systems can be mathematically described as graphs, with a vertex representing a certain state of the system and an edge representing a transition between two states. A computer displaying this text, for instance, is in a defined state represented as a vertex. When the user clicks on a link, the system changes to another state, and this transition is shown as an edge.
Improved graph algorithms
This method is particularly suited for the verification of computer systems. Chatterjee was interested in how fast these verification algorithms work. "Computer systems are getting more complex all the time", the computer scientist notes. "In some algorithmic problems in verification development has been stagnating since the 1990s. A new aspect of this project was to use cutting-edge approaches from graph theory to improve the algorithms. That was a completely new line of attack." Chatterjee emphasises the significance of his cooperation with his project partner Monika Henzinger from the University of Vienna. "For me, that was an intensive learning process. It was intriguing to see how the methods of graph algorithms need to be adapted and expanded in order to arrive at better algorithms for the problems we studied."
Limits, conditions, successes
In that respect, the project was very successful: several speed limits for certain verification algorithms were broken for the first time since the 1990s, for instance involving so-called 'Markov decision processes', which are models containing several options and an element of randomness. "One example for that would be the development of robots", explains Chatterjee. "A robot interacts with an environment which includes uncertainties and it has several options, such as veering to the left or to the right. Markov decision processes provide a model for that." For many applications it is essential to predict in such a model what events will occur with certainty. "The most efficient algorithm for addressing that problem available till now dated back to 1995 and had quadratic complexity", notes Chatterjee. This means that the runtime of the algorithm increases quadratically with the size of the system being verified – hence, a system double in size requires fourfold runtime. "In our project we were able to overcome this limit by using graph algorithm techniques."
Chatterjee is very pleased with the success of the project. "Our two doctoral students, Sebastian Krinninger and Martin Chmelik, also did excellent work, both received prizes for their dissertations", notes Chatterjee. Despite the topical relevance of the subject he underlines that his was a pure basic research project. "Our first project was very theoretical. Now we are trying to explore limits or conditions to see how hard it is going to be to improve our algorithms further. At the same time we want to see how these approaches can be translated into practice."
FWF Austrian Science Fund
The Austrian Science Fund (FWF) is Austria's central funding organization for basic research.
The purpose of the FWF is to support the ongoing development of Austrian science and basic research at a high international level. In this way, the FWF makes a significant contribution to cultural development, to the advancement of our knowledge-based society, and thus to the creation of value and wealth in Austria.
Prof. Krishnendu Chatterjee
Am Campus 1
T +43 / 2243 / 9000 3201
Austrian Science Fund FWF
Haus der Forschung
1090 Vienna, Austria
T +43 / 1 / 505 67 40 - 8111
PR&D – Public Relations for Research and Education
1090 Vienna, Austria
T +43 / 1 / 505 70 44
This release was published on openPR.
Permanent link to this press release:
Please set a link in the press area of your homepage to this press release on openPR. openPR disclaims liability for any content contained in this release.
You can edit or delete your press release Using mathematics to hunt for computer errors here
News-ID: 413758 • Views: 617
More Releases from FWF - Austrian Science Fund
While fear and aggression tend to curb our appetite, sadness and frustration seem to stimulate it. A project funded by the Austrian Science Fund FWF looks into the connections between mood and overeating in healthy and bulimic individuals. We know how it feels to look forward to our favourite dish; we are familiar with the notions of comfort food and feeling butterflies in the stomach instead of hunger. In eating
Neurosciences: a stress test for men and women
Whilst it is true that women and men respond differently to stress, current neuroscientific research only partially confirms traditional gender stereotypes. Other factors heavily contribute to the stress response such as self-esteem, hormones and stress regulation, as has been demonstrated by a project funded by the Austrian Science Fund FWF. How people react to stress is subjective. Gender also plays a fundamental role. Scientific studies have shown that the stress
Researching the grammar of sign language
Like spoken language, sign language has a complex and differentiated structure. One just has to be able to discern and interpret it. With the support of the Austrian Science Fund FWF, a research team from Klagenfurt is working on the elements of a grammar of sign language. It is language that distinguishes Homo sapiens from animals. A complex system in which smaller units combine into larger units, into sentences, into statements.
The many layers of Bella Asmara
Asmara, the capital of Eritrea, is a much admired time capsule reflecting the Italian "dolce vita" of the 1930s. A cluster of modernist buildings has been preserved at the city centre – an Italian futurist vision erected by Mussolini's colonial administration. The postcolonial context of this cultural gem has now been documented in a project funded by the Austrian Science Fund FWF. Asmara, the capital of the young state of Eritrea,
More Releases for Chatterjee
IIM Udaipur has inaugurated two-year MBA programme for the incoming batch of 202 …
Indian Institute of Management Udaipur held its two-year MBA programme’s inauguration followed by three days-long orientation sessions for the incoming 2020-2022 batch with over 375 participants attending the ceremony. The induction was held digitally in the presence of Chief Guest Sonjoy Chatterjee, Chairman & CEO of Goldman Sachs India; Prof Janat Shah, Director, IIM Udaipur; Prof Rezina Sultana, Academic Dean, IIM Udaipur; faculty and incoming students. Addressing the Class of 2022 and
The Infinity School Welcomes Mr. Satyadeep Chatterjee On The Advisory Board- A S …
21 July 2020: The Infinity School, Greater Noida West. The Infinity School in Greater Noida West, recently welcomed Mr. Satyadeep Chatterjee on their advisory board, moving a step closer to their goal of raising kids as future-ready thought leaders having 21st-century skills. Having a vast consulting & industry experience spanning over eighteen years, Mr. Satyadeep Chatterjee has led multiple engagements in corporate & business strategy, supply chain & operations, sales & distribution,
Free Health Camp for elderlies by AK Mishra Foundation in association with Healt …
AK Mishra Foundation in association with Healthy Aging India and Department of Geriatric Medicine, All India Institute of Medical Sciences (AIIMS), New Delhi will organize a free health camp for senior citizens on 18th and 19th February at Vinoba Bhave University, Hazaribagh, Jharkhand. Vinoba Bhave University is a renowned university in Jharkhand which provides impeccable education opportunities to students at Hazaribagh. The event will go from 9am to 5pm on
'Pink' Will Be Screened At UN Headquarters
When Amitabh Bachchan, Taapsee Pannu starrer 'Pink' was released on September 16, 2016 it made a huge box-office collections as well as garnered appreciations from every nook and corner. Aniruddha Roy Chowdhury came up with a strong subject which showcased the harassment faced by women in the society. The three leads of the film Taapsee Pannu, Kirti Kulhari and Andrea Tariang portrayed the victims of the harassment while Angad Bedi was
Eaton names Subhasis Chatterjee Managing Director – Hydraulics, India
Diversified industrial manufacturer Eaton announced that Subhasis Chatterjee has been named as managing director for the company’s Hydraulics business in India. Chatterjee will report to Shyam Kambeyanda, president of Eaton’s Hydraulics business in the Asia Pacific region. Chatterjee succeeds Nitin Chalke who was recently named managing director of Eaton in India. “I am pleased that Subhasis has taken this new leadership role after his diversified global assignments in the Hydraulics
The JK Tyre-MMS Rotax Rookie Cup Hyderabad
HYDERABAD, May 20, 2012 _ Mumbai lad Arya Gandhi of Rayo Racing (206 points) pipped Chennai boy Surya Raguram of Meco Racing by one point (205) to emerge the Junior Max champion in the JK Tyre-MMS Rookie Cup 2012 karting championship at the MMS-Lahari Karting centre here on Sunday. Gandhi, who led consistent Raguram by a single point after three races on Saturday, finished third in Sunday’s opening race which was