Pasar al contenido principal

SAFER-UPV: ANALISIS Y VALIDACION DE SOFTWARE Y RECURSOS WEB

PID2019-104735RB-C41

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

An SMT-Based Concolic Testing Tool for Logic Programs

  • Fortz, Sophie
  • Mesnard, Fred
  • Payet, Etienne
  • Perrouin, Gilles
  • Vanhoof, Wim
  • Vidal, Germán|||0000-0002-1857-6951
[EN] Concolic testing combines symbolic and concrete execution to generate test cases that achieve a good program coverage. Its benefits have been demonstrated for more than 15 years in the case of imperative programs. In this work, we present a concolic-based test generation tool for logic programs which exploits SMT-solving for constraint resolution, Third author is a research associate at FNRS that also supports this work (O05518FRG03). The last author is partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1-R/PID2019-104735RB-C41 and by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust)
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Causal-Consistent Replay Reversible Semantics for Message Passing Concurrent Programs

  • Lanese, Ivan
  • Palacios, Adrián
  • Vidal, Germán|||0000-0002-1857-6951
[EN] Causal-consistent reversible debugging is an innovative technique for debugging concurrent systems. It allows one to go back in the execution focusing on the actions that most likely caused a visible misbehavior. When such an action is selected, the debugger undoes it, including all and only its consequences. This operation is called a causal-consistent rollback. In this way, the user can avoid being distracted by the actions of other, unrelated processes. In this work, we introduce its dual notion: causal-consistent replay. We allow the user to record an execution of a running program and, in contrast to traditional replay debuggers, to reproduce a visible misbehavior inside the debugger including all and only its causes. Furthermore, we present a unified framework that combines both causal-consistent replay and causal-consistent rollback. Although most of the ideas that we present are rather general, we focus on a popular functional and concurrent programming language based on message passing: Erlang., This work has been partially supported by the COST Action IC1405 on Reversible Computation extending horizons of computing. The first author has also been partially supported by INdAM - GNCS 2020 project Sistemi Reversibili Concorrenti: dai Modelli ai Linguaggi. The first and third authors have been also partially supported by French ANR project DCore ANR-18-CE25-0007. The second and third authors have been also partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1-R and PID2019-104735RB-C41, and by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The expression dependence graph

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Pérez-Rubio, Sergio
[EN] The system dependence graph (SDG) is a widely used program representation for the static analysis of programs. In particular, it is the standard way to represent control and flow dependences between the statements of a program. It is at the core of program slicing, a technique that extracts the part of a program that can influence a given program point (the so-called slicing criterion). In this paper, we identify several program slicing situations (e.g., list comprehensions, try-catch and for) ) where the representation provided by the SDG is imprecise, and we present an alternative program representation, which is indeed an extension of the SDG, that solves these situations. We call this extension the expression dependence graph (EDG). The EDG redefines the SDG by increasing the granularity of its nodes to abstract syntax tree (AST) nodes. The implications of this change include an improvement in precision, the appearance of new kinds of dependences (besides control and flow dependences), and the possibility of selecting any (sub)expression as the slicing criterion., This work has been partially supported by grant PID2019-104735RB-C41 funded by MCIN/AEI/10.13039/501100011033, by the Generalitat Valenciana under grant CIPROM/2022/6 (FassLow) , and by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. Carlos Galindo was partially supported by the Spanish Ministerio de Universidades under grant FPU20/03861.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

ReverCSP: Time-Travelling in CSP Computations

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Nishida, Naoki
  • Tamarit, Salvador
[EN] This paper presents reverCSP, a tool to animate both forward and backward CSP computations. This ability to reverse computations can be done step by step or backtracking to a given desired state of interest. reverCSP allows us to reverse computations exactly in the same order in which they happened, or also in a causally-consistent way. Therefore, reverCSP is a tool that can be especially useful to comprehend, analyze, and debug computations. reverCSP is an open-source project publicly available for the community. We describe the tool and its functionality, and we provide implementation details so that it can be reimplemented for other languages., This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1-R and PID2019- 104735RB-C41, and by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Maximal and minimal dynamic Petri net slicing

  • Llorens Agost, María Luisa|||0000-0002-2790-0055
  • Oliver Villarroya, Javier|||0000-0002-1169-1260
  • Silva, Josep|||0000-0001-5096-0008
  • Tamarit, S.
[EN] Context: Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with three other state-of-the-art algorithms have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal., This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grant PID2019-104735RB-C41 and by the European Union's Horizon 2020 research and innovation programme under grant agreement No 952215 (Tailor).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Page-Level Main Content Extraction from Heterogeneous Webpages

  • Alarte-Aleixandre, Julián
  • Silva, Josep|||0000-0001-5096-0008
[EN] The main content of a webpage is often surrounded by other boilerplate elements related to the template, such as menus, advertisements, copyright notices, and comments. For crawlers and indexers, isolating the main content from the template and other noisy information is an essential task, because processing and storing noisy information produce a waste of resources such as bandwidth, storage space, and computing time. Besides, the detection and extraction of the main content is useful in different areas, such as data mining, web summarization, and content adaptation to low resolutions. This work introduces a new technique for main content extraction. In contrast to most techniques, this technique not only extracts text, but also other types of content, such as images, and animations. It is a Document Object Model-based page-level technique, thus it only needs to load one single webpage to extract the main content. As a consequence, it is efficient enough as to be used online (in real-time). We have empirically evaluated the technique using a suite of real heterogeneous benchmarks producing very good results compared with other well-known content extraction techniques., This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1-R and PID2019-104735RB-C41, by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust), and by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Slicing unconditional jumps with unnecessary control dependencies

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Pérez-Rubio, Sergio
[EN] Program slicing is an analysis technique that has a wide range of applications, ranging from compilers to clone detection software, and that has been applied to practically all programming languages. Most program slicing techniques are based on a widely extended program representation, the System Dependence Graph (SDG). However, in the presence of unconditional jumps, there exist some situations where most SDG-based slicing techniques are not as accurate as possible, including more code than strictly necessary. In this paper, we identify one of these scenarios, pointing out the cause of the inaccuracy, and describing the initial solution to the problem proposed in the literature, together with an extension, which solves the problem completely. These solutions modify both the SDG generation and the slicing algorithm. Additionally, we propose an alternative solution, that solves the problem by modifying only the SDG generation, leaving the slicing algorithm untouched., This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1-R and PID2019-104735RB-C41, by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust), and by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Semiautomatic generation and assessment of Java exercises in engineering education

  • Insa Cabrera, David
  • Pérez-Rubio, Sergio
  • Tamarit Muñoz, Salvador
  • Silva, Josep|||0000-0001-5096-0008
[EN] Continuous assessment is essential in education. It should be an integral part of education that provides immediate feedback to students. Unfortunately, the assessment of programming source code is still a hand-operated and error-prone task, and can take weeks before the student gets feedback. This study presents a semiautomatic code assessment method able to automatically apply black-box assessment (which relies on the comparison of input-output pairs) and white-box assessment (which relies on checking different source code properties). The method proposed is a general-purpose assessment system that was originally designated to be used in engineering education, but that can be used in other educational contexts to assist the assessment of any Java programming assignments or exams. The main advantage of this system is that the assessment made is quicker, exhaustive, and objective; and it does not produce false positives. After the application of this method over two years in several real university courses, we have released a public and free implementation. An empirical evaluation of this system estimates that the amount of assessment work automatically done by the tool is over 48%. Additionally, the system has been used to measure the average subjective influence (i.e., assessment errors) introduced by teachers when they assess exams manually., MINECO/AEI/FEDER (EU), Grant/Award Number: TIN2016-76843-C4-1-R; Universitat Politecnica de Valencia, Grant/Award Number: FPI Grant PAID-01-18; Generalitat Valenciana, Grant/Award Number: Prometeo/2019/098 (DeepTrust); TAILOR, EU Horizon 2020, Grant/Award Number: GA No 952215
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Field-sensitive program slicing

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Jens, Krinke
  • Pérez-Rubio, Sergio
[EN] The granularity level of the traditional program dependence graph (PDG) for composite data structures (tuples, lists, records, objects, etc.) is inaccurate when slicing their inner elements. We present the constrained-edges PDG (CE-PDG) that addresses this accuracy problem. The CE-PDG enhances the representation of composite data structures by decomposing statements into a subgraph that represents the inner elements of the structure, and the inclusion and propagation of data constraints along the CE-PDG edges allow for accurate slicing of complex data structures. Both extensions are conservative with respect to the traditional PDG, in the sense that all slicing criteria (and more) that can be specified in the PDG can be also specified in the CE-PDG, and the slices produced with the CE-PDG are always smaller or equal to the slices produced by the PDG. An evaluation of our approach shows a reduction in the size of the slices of around 10%., This work has been partially supported by grant PID2019-104735RB-C41 funded by MCIN/AEI/10.13039/501100011033 and by the Generalitat Valenciana under grant CIPROM/2022/6 (FassLow). Carlos Galindo was partially supported by the Spanish Ministerio de Universidades under grant FPU20/03861.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Program slicing with exception handling

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Pérez-Rubio, Sergio
[EN] Program slicing is a technique for program analysis and transformation with many different applications such as program debugging, program specialization, and parallelization. The system dependence graph (SDG) is the most commonly used data structure for program slicing. In this paper, we show that the presence of exception-handling constructs can make the SDG produce incorrect and sometimes even incomplete slices. We showcase the instances of incorrectness and incompleteness and we propose a framework for correctly handling exception-related instructions, which includes representation of all possible exception throwing and catching mechanisms, and a new kind of control dependence: conditional control dependence; which produces more precise slices in the presence of catch statements., This work is partially supported by the EU (FEDER) and the Spanish MCI/AEI under Grant No.: TIN2016-76843-C4-1-R and PID2019-104735RB-C41, and by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust). Sergio Pérez was partially supported by Universitat Politècnica de València under FPI grant PAID-01-18.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Program slicing of Java programs

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Pérez, Sergio
[EN] Program slicing is a technique to extract the part of the program that can affect the values computed at a given program point (known as the slicing criterion). To represent programs, program slicing uses the System Dependence Graph (SDG), for which several extensions like the Java System Dependence Graph (JSysDG) or the Sub-Statement Linear Dependence Graph (SSLDG) exist to deal with Java object-oriented programs. In this paper, we present an incompleteness result proving that these graphs do not produce complete slices in all cases, and specifically when some object variables are selected as the slicing criterion. We first identify the source of the problem: the representation of dependences between partial definitions of objects is ill-defined in these approaches, leading to a loss of completeness in many cases. To solve this limitation, we extend these representations with the addition of a specific flow dependence for object type variables called object-flow dependence. This extension provides a more accurate flow representation between object variables and its data members and it allows us to obtain complete slices when an object variable is selected as the slicing criterion.(c) 2022 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)., This work has been partially supported by grant PID2019-104735RB-C41 funded by Spanish MCI/AEI/10.13039/501100011033, by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust), and by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. Carlos Galindo was partially supported by the Spanish Ministerio de Universidades under grant FPU20/03861. Sergio Perez was partially supported by Universitat Politecnica de Valencia under FPI grant PAID-01-18.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Reversible Computations in Logic Programming

  • Vidal, Germán|||0000-0002-1857-6951
[EN] In this work, we say that a computation is reversible if one can find a procedure to undo the steps of a standard (or forward) computation in a deterministic way. While logic programs are often invertible (e.g., one can use the same predicate for adding and for subtracting natural numbers), computations are not reversible in the above sense. In this paper, we present a so-called Landauer embedding for SLD resolution, the operational principle of logic programs, so that it becomes reversible. A proof-of-concept implementation of a reversible debugger for Prolog that follows the ideas in this paper has been developed and is publicly available., This work is partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1-R/PID2019-104735RB-C41, by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust), and by the COST Action IC1405 on Reversible Computation - extending horizons of computing.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Concolic Testing in CLP

  • Mesnard, Fred
  • Payet, Etienne
  • Vidal, Germán|||0000-0002-1857-6951
[EN] Concolic testing is a popular software verification technique based on a combination of concrete and symbolic execution. Its main focus is finding bugs and generating test cases with the aim of maximizing code coverage. A previous approach to concolic testing in logic programming was not sound because it only dealt with positive constraints (by means of substitutions) but could not represent negative constraints. In this paper, we present a novel framework for concolic testing of CLP programs that generalizes the previous technique. In the CLP setting, one can represent both positive and negative constraints in a natural way, thus giving rise to a sound and (potentially) more efficient technique. Defining verification and testing techniques for CLP programs is increasingly relevant since this framework is becoming popular as an intermediate representation to analyze programs written in other programming paradigms., This author has been partially supported by EU (FEDER) and Spanish MCI/AEI under grants TIN2016-76843-C4-1-R and PID2019-104735RB-C41, and by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Reversible CSP Computations

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Nishida, Naoki
  • Tamarit, Salvador
[EN] Reversibility enables a program to be executed both forwards and backwards. This ability allows programmers to backtrack the execution to a previous state. This is essential if the computation is not deterministic because re-running the program forwards may not lead to that state of interest. Reversibility of sequential programs has been well studied and a strong theoretical basis exists. Contrarily, reversibility of concurrent programs is still very young, especially in the practical side. For instance, in the particular case of the Communicating Sequential Processes (CSP) language, reversibility is practically missing. In this article, we present a new technique, including its formal definition and its implementation, to reverse CSP computations. Most of the ideas presented can be directly applied to other concurrent specification languages such as Promela or CCS, but we center the discussion and the implementation on CSP. The technique proposes different forms of reversibility, including strict reversibility and causal-consistent reversibility. On the practical side, we provide an implementation of a system to reverse CSP computations that is able to highlight the source code that is being executed in each forwards/backwards computation step, and that has been optimized to be scalable to real systems., A preliminary version of this work was presented at the 12th Conference on Reversible Computation [31]. The authors would like to thank the anonymous reviewers for their useful comments and constructive feedback that helped them to improve this work. This work was supported in part by the EU (FEDER) and the Spanish MCI/AEI under Grant TIN2016-76843-C4-1-R and Grant PID2019-104735RB-C41, in part by the Generalitat Valenciana under Grant Prometeo/2019/098 (DeepTrust), in part by JSPS KAKENHI under Grant JP17H01722, and in part by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA 952215.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Exception-sensitive program slicing

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Pérez, Sergio
[EN] Program slicing is a technique for program analysis and transformation with many different applications such as program debugging, program specialisation, and parallelisation. The system dependence graph (SDG), the most commonly used data structure for program slicing, has been extended in several ways to manage exception handling constructs. In this paper, however, we show that the presence of exception-handling constructs can make even the extended SDG produce incorrect and incomplete slices. To solve this situation, we survey the current state of the art and merge and extend different approaches (that treat throws, try-catch, etc.) to produce a version of the SDG that is able to manage all of them, that always produces complete slices, and that increases its precision keeping the same time complexity. An interesting side result is the discovering of a new kind of control dependence: conditional control dependence, which is needed to properly represent catch statements.(c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)., This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grant PID2019-104735RB-C41, and by the Generalitat Valencianaunder grant Prometeo/2019/098 (DeepTrust). Sergio Perez was partially supported by Universitat Politecnica de Valenciaunder FPI grant PAID01-18. Carlos Galindo was partially supported by the Spanish Ministerio de Universidades under grant FPU20/03861 and by the Generalitat Valenciana under grant ACIF/2021/155.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A distribution semantics for probabilistic term rewriting

  • Vidal, Germán|||0000-0002-1857-6951
[EN] Probabilistic programming is becoming increasingly popular thanks to its ability to specify problems with a certain degree of uncertainty. In this work, we focus on term rewriting, a wellknown computational formalism. In particular, we consider systems that combine traditional rewriting rules with probabilities. Then, we define a novel "distribution semantics" for such systems that can be used to model the probability of reducing a term to some value. We also show how to compute a set of "explanations" for a given reduction, which can be used to compute its probability in a more efficient way. Finally, we illustrate our approach with several examples and outline a couple of extensions that may prove useful to improve the expressive power of probabilistic rewrite systems., This work has been partially supported by grant PID2019-104735RB-C41 funded by MICIU/AEI/10.13039/501100011033, by the Generalitat Valenciana under grant CIPROM/2022/6 (FassLow) , and by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Data Dependence for Object-Oriented Programs

  • Galindo, Carlos|||0000-0002-3569-6218
  • Silva, Josep|||0000-0001-5096-0008
  • Pérez-Rubio, Sergio
[EN] The System Dependence Graph (SDG) is a program representation used in several static analyses. In particular, it is the basis of program slicing, a technique that extracts the part of the program that may directly or indirectly affect the values computed at a given program point (known as the slicing criterion). Several approaches have enhanced the SDG representation to deal with object-oriented situations like inheritance, polymorphism, or dynamic bindings. Currently, the most advanced approach is the Java System Dependence Graph (JSysDG), which subsumes previous approaches and that is able to represent all those situations. In this paper, we show that even the JSysDG does not produce complete slices in all cases when some object variables are selected as the slicing criterion. To solve this limitation, we first identify the source of the problem: the representation of dependences between partial definitions of objects is insufficient in the JSysDG, leading to a loss of completeness in many cases. Then, we extend the JSysDG with the addition of a specific flow dependence for object type variables called object-flow dependence. This extension provides a more accurate flow representation between object variables and its data members and allows us to obtain complete slices when an object variable is considered as slicing criterion., This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grants TIN2016-76843-C4-1- R and PID2019-104735RB-C41, by the Generalitat Valenciana under grant Prometeo/2019/098 (DeepTrust), and by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. Sergio Pérez was partially supported by Universitat Politècnica de València under FPI grant PAID-01-18.