Leen Lambers

Leen Lambers, Lucas Sakizloglou, Taisiya Khakharova et al.

We present the first systematic approach to static and dynamic taint analysis for Graph APIs focusing on broken access control. The approach comprises the following. We taint nodes of the Graph API if they represent data requiring specific privileges in order to be retrieved or manipulated, and identify API calls which are related to sources and sinks. Then, we statically analyze whether a tainted information flow between API source and sink calls occurs. To this end, we model the API calls using graph transformation rules. We subsequently use Critical Pair Analysis to automatically analyze potential dependencies between rules representing source calls and rules representing sink calls. We distinguish direct from indirect tainted information flow and argue under which conditions the Critical Pair Analysis is able to detect not only direct, but also indirect tainted flow. The static taint analysis (i) identifies flows that need to be further reviewed, since tainted nodes may be created by an API call and used or manipulated by another API call later without having the necessary privileges, and (ii) can be used to systematically design dynamic security tests for broken access control. The dynamic taint analysis checks if potential broken access control risks detected during the static taint analysis really occur. We apply the approach to a part of the GitHub GraphQL API. The application illustrates that our analysis supports the detection of two types of broken access control systematically: the case where users of the API may not be able to access or manipulate information, although they should be able to do so; and the case where users (or attackers) of the API may be able to access/manipulate information that they should not.

Alexander Lauer, Jens Kosiol, Leen Lambers et al.

Conflict and dependency analysis is an important static analysis tool that provides an overview of the potential interactions of (graph) transformation rules. This analysis is based on critical pairs and initial conflicts, which represent conflicting transformations in a minimal context. However, the crucial information about a conflicting transformation pair is contained in much smaller structures, called disabling/conflict essences in existing research. Recently, we introduced disabling essences for rules with application conditions which contain the information on how an application condition can be violated by another rule. In this paper, we extend the notion of disabling essences to support not only application conditions in Alternating Quantifier Normal Form, but also arbitrary nested conditions. We introduce (symbolic) conflict essences that are constructed from disabling essences and which capture the interaction between two rules. We show that a transformation pair is parallel dependent if and only if a symbolic conflict essence can be embedded into it and relate symbolic conflict essences to initial conflicts for transformation rules with application conditions. We present our results for adhesive HLR categories, which includes several types of graph-like structures.

Taisiya Khakharova, Lucas Sakizloglou, Leen Lambers

Sepsis is a serious, life-threatening condition. When treating sepsis, it is challenging to determine the correct amount of intravenous fluids and vasopressors for a given patient. While automated reinforcement learning (RL)-based methods have been used to support these decisions with promising results, previous studies have relied on relational data. Given the complexity of modern healthcare data, representing data as a graph may provide a more natural and effective approach. This study models patient data from the well-known MIMIC-III dataset as a heterogeneous graph that evolves over time. Subsequently, we explore two Graph Neural Network architectures - GraphSAGE and GATv2 - for learning patient state representations, adopting the approach of decoupling representation learning from policy learning. The encoders are trained to produce latent state representations, jointly with decoders that predict the next patient state. These representations are then used for policy learning with the dBCQ algorithm. The results of our experimental evaluation confirm the potential of a graph-based approach, while highlighting the complexity of representation learning in this domain.

Reiko Heckel, Leen Lambers, Maryam Ghaffari Saadat

The paper summarises the contributions in a session at GCM 2019 presenting and discussing the use of native and translation-based solutions to common analysis problems for Graph Transformation Systems (GTSs). In addition to a comparison of native and translation-based techniques in this area, we explore design choices for the latter, s.a. choice of logic and encoding method, which have a considerable impact on the overall quality and complexity of the analysis. We substantiate our arguments by citing literature on application of theorem provers, model checkers, and SAT/SMT solver in GTSs, and conclude with a general discussion from a software engineering perspective, including comments from the workshop participants, and recommendations on how to investigate important design choices in the future.