Project

Back to overview

ReSpec: Characterizing and Using the Intrinsic Redundancy of Software

English title ReSpec: Characterizing and Using the Intrinsic Redundancy of Software
Applicant Carzaniga Antonio
Number 146607
Funding scheme Project funding (Div. I-III)
Research institution Istituto di sistemi informatici (SYS) Facoltà di scienze informatiche
Institution of higher education Università della Svizzera italiana - USI
Main discipline Information Technology
Start/End 01.05.2013 - 31.08.2016
Approved amount 196'665.00
Show all

Keywords (4)

specifiche; ridondanza intrinseca; affidabilità del software; oracoli per la verifica del software

Lay Summary (Italian)

Lead
Abbiamo osservato sperimentalmente che il software possiede la capacità di svolgere certe funzioni con codici diversi, non duplicati intenzionalmente dai progettisti ma piuttosto prodotti al seguito di un normale sviluppo modulare del software. Questo è quello che chiamiamo ridondanza intrinseca, la quale può essere utilizzata per rendere il software più robusto. Ora vogliamo capire le origini e le caratteristiche salienti di questa ridondanza del software per poterla utilizzare al meglio.
Lay summary
Obiettivi della ricerca

Lo scopo del progetto ReSpec è di esaminare e comprendere la ridondanza del software come fenomeno e soprattutto come risorsa potenzialmente utile.  Inizialmente ci proponiamo di formalizzare il concetto di ridondanza intrinseca del software così da poterla identificare e misurare in modo automatico o semi-automatico.  Poi ci proponiamo di studiare come questa ridondanza si manifesta in vari progetti software, relazionandola ad altri aspetti importanti quali il tipo di applicazione e il linguaggio di programmazione.  Poi ci proponiamo di identificare le potenzialità d'uso di questa ridondanza per migliorare la qualità del software e in particolare per automatizzare alcuni aspetti del controllo di qualità.

Contesto socio-scientifico

Data la sempre crescente centralità del software in sistemi di ogni genere, dai trasporti all'energia alla produzione alla gestione, questa ricerca ha potenziali applicazioni al di là dello sviluppo del software stesso.  L'obiettivo di lungo termine è di rendere il software più affidabile e allo stesso tempo di ridurre i costi di sviluppo.  Quindi, più in generale, questa ricerca contribuirà anche indirettamente allo sviluppo di nuovi prodotti e processi ad alto contenuto tecnologico.

Direct link to Lay Summary Last update: 21.04.2013

Responsible applicant and co-applicants

Employees

Name Institute

Publications

Publication
Automatic Generation of Oracles for Exceptional Behaviors
Goffi Alberto, Gorla Alessandra, Ernst Michael D., Pezzè Mauro (2016), Automatic Generation of Oracles for Exceptional Behaviors, in Proceedings of the 25th International Symposium on Software Testing and Analysis, Saarbrücken, GermanyACM, 2016.
Synthesis of Equivalent Method Calls in Guava
Mattavelli Andrea, Goffi Alberto, Gorla Alessandra (2015), Synthesis of Equivalent Method Calls in Guava, in Proceedings of the 7th International Symposium on Search-Based Software Engineering, Bergamo, ItalySpringer International Publishing, Switzerland.
Cross-checking Oracles from Intrinsic Software Redundancy
Carzaniga Antonio, Goffi Alberto, Gorla Alessandra, Mattavelli Andrea, Pezzè Mauro (2014), Cross-checking Oracles from Intrinsic Software Redundancy, in Proceedings of the 36th International Conference on Software Engineering , Hyderabad, IndiaACM, New York, NY, USA.
Automatic Generation of Cost-effective Test Oracles
Goffi Alberto (2014), Automatic Generation of Cost-effective Test Oracles, in Companion Proceedings of the 36th International Conference on Software Engineering, Hyderabad, IndiaACM, New York, NY, USA.
Search-Based Synthesis of Equivalent Method Sequences
Goffi Alberto, Gorla Alessandra, Mattavelli Andrea, Pezzè Mauro, Tonella Paolo (2014), Search-Based Synthesis of Equivalent Method Sequences, in Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, Hong Kong, ChinaACM, New York, NY, USA.

Collaboration

Group / person Country
Types of collaboration
Michael D. Ernst United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
- Exchange of personnel
Alexander L. Wolf Great Britain and Northern Ireland (Europe)
- in-depth/constructive exchanges on approaches, methods or results
Alessandra Gorla Spain (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
- Research Infrastructure

Scientific events

Active participation

Title Type of contribution Title of article or contribution Date Place Persons involved
25th International Symposium on Software Testing and Analysis Talk given at a conference Automatic generation of oracles for exceptional behaviors 18.07.2016 Saabrücken, Germany Goffi Alberto;
IMDEA Software Institute Invited Talk Individual talk Exploiting Intrinsic Redundancy to Automatically Generate Test Oracles 19.06.2015 Madrid, Spain Goffi Alberto;
36th International Conference on Software Engineering Talk given at a conference Cross-checking oracles from intrinsic software redundancy 31.05.2014 Hyderabad, India Goffi Alberto;
Doctoral Symposium, 36th International Conference on Software Engineering Talk given at a conference Automatic generation of cost-effective test oracles 31.05.2014 Hyderabad, India Goffi Alberto;


Associated projects

Number Title Start Funding scheme
138006 SHADE: a Self HeAling DEsign methodology 01.11.2011 Project funding (Div. I-III)

Abstract

We propose to study the redundancy of software systems. To put it simply and informally, a system is redundant when it is capable of performing the same logical computation or state transition through the execution of two or more pieces of code that are at least partially different and idependent. In particular, we are interested in redundancy that is not deliberately incorporated into a system but that is instead an intrinsic feature of the software. We have observed experimentally that this form of redundancy is indeed present to a significant extent in some systems. We now propose to study this redundancy systematically.The starting point of our research will be a formalization of the intuitive notion of redundancy. As we said informally, a software system is redundant when it can do the same thing in different ways. We will develop this notion more formally by defining, on the one hand, what it means for two executions to do the same thing, and on the other hand how two executions can be differentiated and to what extent they can be deemed independent. In particular, our model of redundancy will be based on the notion of observable equivalence of executions combined with various distance metrics over execution traces. This model will then be the basis for a dual-track research project.In the first track we propose to study the prevalence, the nature, and the origin of intrinsic redundancy in modern software systems. In other words, within this track we propose to look at intrinsic redundancy as a phenomenon. We will try to characterize it qualitatively and quantitatively and to correlate it with important features of the design of software systems as well as with other technical or organizational aspects of the software and its development process. For example, we intuitively hypothesize, and will attempt to demonstrate experimentally, that intrinsic redundancy is more prevalent in highly modular software systems, where the functionality of the system results from the integration of component frameworks and libraries. Other aspects of the system that might correlate with intrinsic redundancy are specific architectures or specific architectural components (e.g., event-driven architectures, GUI) and specific application domains (e.g., data management systems, collection libraries) and also technical aspects such as the programming language (more or less object-oriented, dynamic vs. static typing).In a second parallel track we propose to develop formalisms and techniques to capture, express, and ultimately exploit intrinsic redundancy. In other words, within this track we propose to look at intrinsic redundancy as a tool. We will first try to capture and express redundancy in the form of specifications of equivalent behaviors with different implementations. Our intuition is that we can draw from techniques developed in diverse fields such as compiler optimization, refactoring, and also some recent developments in model checking, particularly on simulation distances. Both compiler optimization and refactoring amount to rewriting code through transformations that might lead to desirable non-functional properties while preserving the program semantics. Furthermore, such transformations could be combined with quantitative measures of the difference between the original program and the transformed program so as to inform the specific strategies by which the transformations would be applied. In short, a redundancy specification will identify semantics-preserving code-level transformations that also express and somehow quantify the potential benefits of each transformation.Having developed appropriate forms of redundancy specifications, and assuming that some software systems indeed possess significant levels of intrinsic redundancy, we will study ways to exploit that redundancy. In the context of other research projects, we have used this redundancy to augment systems with a form of self-healing behavior, whereby redundant code is used to work around runtime failures. One rather straightforward extension of this work is to use redundancy to improve performance or to address other non-functional properties. However, we also see and propose to study several and diverse potential uses of intrinsic redundancy. One such use is to implement implicit automatic oracles for generated tests. Another idea that also relates to testing and debugging is to amplify generated tests through a combinatorial substitution of equivalent sequences of calls. Such amplified tests could then be used with many testing and fault-localization techniques. Yet another idea is to use redundancy specifications in model checking, for example to reuse invariants computed for specific transitions with equivalent transitions. In general, we see redundancy specifications as yet another form of behavioral specification that may therefore be useful in several forms of program analyses.
-