Skip to main content

SOLUCIONES EFECTIVAS BASADAS EN LA LOGICA

TIN2015-69175-C4-2-R

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2015
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Dirección General de Investigación Científica y Técnica
Beneficiary centre UNIVERSIDAD COMPLUTENSE DE MADRID

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

Docta Complutense
Publication Contribución de congreso (ConferenceOutput)

Conditional dynamic partial order reduction and optimality results

  • Isabel Márquez, Miguel
Testing concurrent systems requires exploring all possible nondeterministic interleavings that the concurrent execution may have, as any of the interleavings may reveal an erroneous behaviour of the system. This introduces a combinatorial explosion on the number of states that must be considered, which leads often to a computationally intractable problem. In the present PhD thesis, this challenge will be addressed through the development of new Partial Order Reduction techniques (POR). The cornerstone of POR theory is the notion of independence, that is used to decided whether each pair of concurrent events p and t are in a race and thus both executions p · t and t · p must be explored. A fundamental goal of this thesis is to introduce notions of conditional independence –which ensure the commutativity of the considered events p and t under certain conditions that can be evaluated in the explored state– with a DPOR algorithm in order to alleviate the combinatorial explosion problem. The new techniques that we propose in the thesis have been implemented within the SYCO tool. We have carried out accompanying experimental evaluations to prove the effectiveness and applicability of the proposed techniques. Finally, we have successfully verified a range of properties for several case studies of Software-Defined Networks to illustrate the potential of the approach, scaling to larger networks than related techniques.
Docta Complutense
Publication Contribución de congreso (ConferenceOutput)

Constrained Dynamic Partial Order Reduction

  • Albert Albiol, Elvira María
  • Gómez-Zamalloa Gil, Miguel
  • Isabel Márquez, Miguel
  • Rubio, Albert
The cornerstone of dynamic partial order reduction (DPOR) is the notion of independence that is used to decide whether each pair of concurrent events p and t are in a race and thus both p · t and t · p must be explored. We present constrained dynamic partial order reduction (CDPOR), an extension of the DPOR framework which is able to avoid redundant explorations based on the notion of conditional independence— the execution of p and t commutes only when certain independence constraints (ICs) are satisfied. ICs can be declared by the programmer, but importantly, we present a novel SMT-based approach to automatically synthesize ICs in a static pre-analysis. A unique feature of our approach is that we have succeeded to exploit ICs within the state-of-the-art DPOR algorithm, achieving exponential reductions over existing implementations.
Docta Complutense
Publication Contribución de congreso (ConferenceOutput)

Combining Static Analysis and Testing for Deadlock Detection

  • Albert Albiol, Elvira María
  • Isabel Márquez, Miguel
  • Gómez-Zamalloa Gil, Miguel
Static deadlock analyzers might be able to verify the absence of deadlock. However, they are usually not able to detect its presence. Also, when they detect a potential deadlock cycle, they provide little (or even no) information on their output. Due to the complex flow of concurrent programs, the user might not be able to find the source of the anomalous behaviour from the abstract information computed by static analysis. This paper proposes the combined use of static analysis and testing for effective deadlock detection in asynchronous programs. When the program features a deadlock, our combined use of analysis and testing provides an effective technique to catch deadlock traces. While if the program does not have deadlock, but the analyzer inaccurately spotted it, we might prove deadlock freedom.