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: 917
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
Thoracic Ring Forceps Market Key Companies, Revenue Share Analysis, Size Outlook …
The Thoracic Ring Forceps Market Report contains compounded annual growth rate (CAGR%), which is calculated for regional markets and each segment-wise, and includes historical, current, and projected data for the years 2022 to 2029. The study looked at the industry's revenue & In-depth primary and secondary data analysis is covered in the research report. It also examines numerous industrial dynamics, such as those affecting the industry's drivers, constraints, trends, and
Sternal Distractor Market Trends and Forecast Report 2022 | By Players, Types, A …
The QY Research released a latest market research report on the global and United States Sternal Distractor market, which is segmented by region (country), players, by Type and by Application. Players, stakeholders, and other participants in the global Sternal Distractor market will be able to gain the upper hand as they use the report as a powerful resource. The segmental analysis focuses on revenue and forecast by region (country), by Type 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,
Satyamoy Chatterjee and Madhav Kaushik from Analyttica Datalab Inc. demonstrated …
Analyttica Datalab's innovative AI/ML platform ATH Precision, nominated under the category of 'Innovation in AI Data Science' in Aegis Graham Bell Awards was demonstrated during the award ceremony. 20th January 2020, Bengaluru Analyttica Datalab, a tech-enabled solutions company from Bengaluru, presented about their AI/ML platform ATH Precision at Graham Bell Awards. This Award is intended to promote innovations in the IT, Telecom, SMAC domain, and Exponential Technologies to provide recognition for outstanding
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