# Policy-Based Slicing ofHibernate Query Language

Angshuman Jana, Raju Halder, Nabendu Chaki, Agostino Cortesi

► To cite this version:

Angshuman Jana, Raju Halder, Nabendu Chaki, Agostino Cortesi. Policy-Based Slicing ofHibernate Query Language. 14th Computer Information Systems and Industrial Management (CISIM), Sep 2015, Warsaw, Poland. pp.267-281, 10.1007/978-3-319-24369-6_22. hal-01444471

HAL Id: hal-01444471

https://inria.hal.science/hal-01444471

Submitted on 24 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Policy-based Slicing ofHibernate Query Language

Angshuman Jana¹, Raju Halder¹, Nabendu Chaki², and Agostino Cortesi³

1. Indian Institute of Technology Patna, India, {ajana.pcs13, halder}@iitp.ac.in

2 University of Calcutta, India, nabendu@ieee.org

3 Università Ca' Foscari Venezia, Italy, cortesi@unive.it

**Abstract.** This paper introduces a policy-based slicing ofHibernate Query Language (HQL) based on a refined notion of dependence graph. The policies are defined on persistent objects, rather than transient objects, which are stored in an underlying database. We extend the Class Dependence Graph (CIDG) of object-oriented languages to the case of HQL, and we refine it by applying semantics-based Abstract Interpretation framework. This leads to a slicing refinement of HQL programs, producing more precise slices w.r.t. policies and we refine by using semantics equivalence, according to the Abstract Interpretation framework.

**Key words:** Program Slicing;Hibernate Query Language; Dependence Graphs; Abstract Interpretation

# 1 Introduction

Program slicing is a widely used static analysis technique which extracts from programs a subset of statements which is relevant to a given behavior [24]. Some of its worth mentioning applications are debugging, testing, code-understanding, code-optimization, etc. [21, 23]. Many program slicing algorithms are proposed during last four decades, referring to various language paradigms, such as imperative, object-oriented, functional, logical, etc. [9, 22–24]. Recently, [10, 25] extended the slicing approaches to the case of applications interacting with external database states. Various forms of program slicing, like static, dynamic, quasi-static, conditioned, etc. are proposed by tuning it towards specific program analysis aim [23].

Hibernate query language (HQL) is an Object-Relational Mapping (ORM) language which remedies the paradigm mismatch between object-oriented languages and relational database models [2]. Various Session methods are used to convert transient objects into persistent ones by propagating their states from memory to the database (or vice versa) and to synchronize both states when a change is made to persistent objects. HQL has gained popularity to software developers in recent years as it provides a unified platform to develop database applications without knowing much details about the database.

Reduction of software failure rate which may happen due to the frequent change of enterprise policies or customers requirements, always remains a serious challenge in software industry [8]. Let us consider an enterprise scenario where new policies are often defined or existing policies are often modified in order to ensure that the real business-data meet business challenges and
goals. This forces software developers to maintain and incorporate appropri-
ate changes to the associated program code even after their deployment in
real world. Since new or modified policies may also lead to an inconsistent
database state, the identification of inconsistent database parts w.r.t. the policies
is also an important issue. This motivates us to propose a slicing framework for
HQL programs, aiming at extracting a subset of program statements affecting
enterprise-policies defined on underlying databases. Unfortunately none of the
existing approaches are directly applicable to the case of HQL where high-level
variables interact with database attributes through hibernate (Session) inter-
face – particularly when we slice HQL programs w.r.t. the behavior of persistent
objects rather than just transient objects.

The main contributions in this paper are:

1. We construct syntax-based dependence graph of HQL, considering (a) intra-class intra-method dependences, (b) intra-class inter-method dependences, (c) inter-class inter-method dependences, and (d) session-database dependences.

2. We apply semantics-based analysis to refine syntax-based dependence graphs of HQL. To this aim, we define an abstract semantics of Hibernate Session methods in a relational abstract domain (the domain of polyhedra).

3. Finally, we propose a policy-based slicing technique on semantically refined dependence graph.

The structure of the rest of paper is as follows: Section 2 describes a running example. In section 3, we describe the syntax-based dependence graphs of HQL. A semantics-based refinement approach of syntax-based dependence graphs is presented in section 4. Section 5 illustrates the running example. Finally, section 6 concludes the work.

## 2 A Running Example

Consider an enterprise information system where the HQL program Prog (Fig-
ure 1(a)) performs three different operations (select, update, delete) on employ-
ees information stored in the database dB (Tables 1(b) and 1(c)) based on the
user choice. Observe that the fields eid, jid, sal, age of POJO class emp in Prog
correspond to the attributes teid, tjid, tsal, tage of dB table temp respectively.
Similarly the fields jobid, jname, jcat, maxsl of POJO class Job in Prog corre-
spond to the attributes tjobid, tjname, tjcat, tmaxsl of dB table tjob respectively.
This mapping is defined in a configuration file of hibernate framework in XML
format. Let us suppose that the company decides to introduce a new policy ψ₁
which respects the consistency of employees salary structure, defined below:

> The salary of employees of age less or equal to 40 cannot have a salary greater
> than 75% of the maximum salary of the same category.

The policy is defined on the persistent objects which have permanent repre-
sentation in the dB. We observe that Prog may violate ψ₁ because statement 16
updates employee's salary without checking his/her age.

Our slicing algorithm will allow us to identify the subset of HQL statements
responsible for such policy violation.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Running example</figcaption></figure>

3 Syntax-based Dependence Graph of HQL

In this section, we extend the notion of dependence graph representation to the
case of HQL. Let us describe its construction using our running example whose
dependence graph is depicted in Figure 2. We consider the following three types
of dependences in HQL programs:

**Intra-class Intra-method Dependences:** These represent the dependences within the same method of a class, and it follows the Program Dependence Graph-based approach [20]. We denote these dependences by dotted edges. Edges 7 - 13, 7 - 17, 7 - 8, 18 - 19, etc. in Figure 2 are of this type.

**Intra-class Inter-method Dependences:** These represent the dependences between statements of two different methods within same class and are constructed by following System Dependence Graph-based approach [13]. We denote these dependences by long-dash-dotted edges. There is no edge of this type in Figure 2.

**Inter-class Inter-method Dependences:**

*Through transient objects.* Inter-class Inter-method dependences occur in OOP when a method in one class calls another method in other class. This is done by
calling the method through an object of the called-class. Therefore, additional
in-parameters corresponding to the object-fields through which the method is
called, must be considered [16]. Note that, in this scenario, a constructor-call
during object creation is also a part of the graph which follows the same repre-
sentation as of other inter-class inter-method calls. We denote these dependences
by long-dash-dotted edges (as in the case of Intra-class Inter-method Depen-
dences). Edges 3 - 4, 5 - 21, 6 - 20, 5 - 6, 4 - 5, etc. in Figure 2 are of this type.
Observe that node 4 calls "configure()" method on the object "cfg" which is
received from node 3. It configures the "cfg" object using "XML" file and acts
as a source for newly-configured "cfg" object. For the sake of simplicity, we
do not include here the details of the calling scenario at node 4. Similarly, we
hide the details of the calling-scenarios at nodes 5 (which creates the session
object by calling openSession()), 6 (which creates the transaction object by
calling beginTransaction()), 20 (when calling commit()) and 21 (when calling
close()) respectively.

Through session objects. Various Session methods are used to convert objects from transient state to persistent state and to perform various operations, like select, update, delete on the persistent objects in the database. In other words,Hibernate Session serves as an intermediate way for the interaction between high-level HQL variables and the database attributes. As creation of a Session object implicitly establishes connection with the database, we consider the nodes which create Session objects as the sources of the database (hence database-attributes). For instance, in Figure 2 the node 5 acts as a source of dB. When Session methods (save(), creatQuery()) are called through Session objects, either a transient object (in case of save()) or an object-oriented variant of SQL statement (in case of createQuery()) are passed as a parameter. For instance, see nodes 10, 16, 19. The presence of HQL variables in the parameter which have mapping with database attributes leads to a number of dependences shown by dash-lines between 5 - 10, 5 - 16 and 5 - 19. We call such depen-dences as session-database dependences. These edges are labeled with used- and defined- HQL variables present in the parameter. For instance, in case of "obj" passed to save(), all database attributes corresponding to object fields act as defined variables. Similarly, in case of update and delete as parameters in the createQuery(), the variables in the WHERE clause act as used variables and the variables in the action part act as defined variables. In case of select, all variables in the parameter act as used variables.

Observe that for the sake of simplified representation, we hide the detail
calling scenario of "createQuery()" by nodes 10, 16, 19. The edges connecting
node 5 and dB indicates the propagation and synchronization of memory and
database states. Although we connect node 4 with XML file "hibernate.cfg.xml"
by an edge, it has no role in slicing and we may omit it also.

4 Semantics-based Refinement of HQL Dependence Graphs

The syntax-based dependence graphs represent dependences based on the syn-
tactic presence of a variable in the definition of another variables. However, this
<figure><img src="image_3.png" /><figcaption>Fig. 2: Dependence Graph of the class "service" (Figure 1)</figcaption></figure>

is not the case always if we focus on the actual values instead of variables. For
instance, although the expression "e = x² + 4w mod 2 + z" syntactically depends
on w, semantically there is no dependency as the evaluation of "4w mod 2" is
always zero. This motivate researchers towards semantics-based dependence
computation [12, 17].

In [12], authors applied three notions: Semantic relevancy, Semantic data-dependences and conditional dependences. This leads to a refinement of syntax-based dependence graphs into more refined semantic-based dependence graphs, producing more precise slices.

The extension of these notions to the case of HQL is not straight-forward
because of the existence of transient objects, persistent objects and Session
methods. Therefore, we have to treat transient objects and persistent objects
differently when we apply these semantics-based computations to HQL.

In the rest of this section, we use the following: Let $Var$ and $Val$ be the set of variables and the domain of values. The set of states is defined as $\Sigma = Var \mapsto Val_{\perp}$, where by $Val_{\perp}$ we denote $Val \cup \{\perp\}$ and $\perp$ is undefined value.

**4.1 Semantic relevancy of HQL statements w.r.t policies**

Consider the following HQL statement on the POJO class Cls which corre-
sponds to the database table Tab in Figure 3(a).

Q = ses.CreateQuery(UPDATE Cls SET age = age+1 WHERE age ≤60).executeUpdate()

Consider a company policy ψ₂ (defined on Tab) which says that employees ages must belong to the range 18 and 62 (i.e. 18 ≤ tage ≤ 62). We denote by σ<sub>D</sub> the state of the database D which includes the state of Tab. The semantics<sup>4</sup> of Q in σ<sub>D</sub>, i.e.
<table><caption>(a) Table Tab</caption><thead><tr><td>teid</td><td>tsal</td><td>tage</td></tr></thead><tbody><tr><td>1</td><td>1200</td><td>55</td></tr><tr><td>2</td><td>1600</td><td>62</td></tr><tr><td>3</td><td>2000</td><td>45</td></tr><tr><td>4</td><td>800</td><td>18</td></tr></tbody></table>

<table><caption>(b) Result after execution of
Q on Tab</caption><thead><tr><td>teid</td><td>tsal</td><td>tage</td></tr></thead><tbody><tr><td>1</td><td>1200</td><td>56</td></tr><tr><td>2</td><td>1600</td><td>62</td></tr><tr><td>3</td><td>2000</td><td>46</td></tr><tr><td>4</td><td>800</td><td>19</td></tr></tbody></table>

<table><caption>(c) Abstract table Tab<sup>#</sup> corresponding to Tab</caption><thead><tr><td>teid<sup>#</sup></td><td>tsal<sup>#</sup></td><td>tag<sup>e<sup>#</sup></sup></td></tr></thead><tbody><tr><td>[1, 4]</td><td>[800, 2000]</td><td>[18, 62]</td></tr></tbody></table>

<table><caption>(d) Result after execution of
Q<sup>#</sup> on Tab<sup>#</sup></caption><thead><tr><td>teid<sup>#</sup></td><td>tsal<sup>#</sup></td><td>tag<sup>e<sup>#</sup></sup></td></tr></thead><tbody><tr><td>[1, 4]</td><td>[800, 2000]</td><td>[19, 62]</td></tr></tbody></table>

<caption>Fig. 3: Concrete and Abstract Query Semantics.</caption>

$S[[Q]]\sigma_D$ yields the result shown in Figure 3(b). We observe that the policy $\psi_2$ is satisfied before and after the execution of Q, i.e. $\psi_2(\sigma_D) = \psi_2(S[[Q]]\sigma_D)$. Therefore, Q is irrelevant w.r.t. $\psi_2$, assuming $\sigma_D$ is the only state that occurs at the program point of Q.

Although this example is trivial to compute the irrelevancy of Q in concrete domain, in case of very large database (or even when database state depends on run-time inputs) the irrelevancy can be computed in an abstract domain of interest following the Abstract Interpretation framework [6]. The Abstract Interpretation framework is a semantics-based overapproximation technique to infer program's behavior during static time. The aim is to lift concrete semantics to an abstract setting by replacing concrete values by suitable properties of interest, and simulating the concrete operations by sound abstract operations. The mapping between concrete semantics domain ($D^c$) and abstract semantics domain ($D^a$) is formalized by Galois Connection $\langle D^c, \alpha, \gamma, D^a \rangle$, where $\alpha: D^c \to D^a$ and $\gamma: D^a \to D^c$ represent concretization and abstraction functions respectively.

To illustrate, let us consider the abstract domain of intervals. The abstract table Tab<sup>#</sup> corresponding to Tab in the domain of intervals is shown in Table 3(c). The corresponding abstract state which includes Tab<sup>#</sup> is denoted by $\sigma_D^#$. The abstract semantics $S^#[[Q^#]]\sigma_D^#$ where $Q^#$ is

`ses.CreateQuery (UPDATE cls# SET age#=age#+[1,1] WHERE age# <= [60,60]).executeUpdate()`

yields the abstract result depicted in Figure 3(d). We observe that $\psi_2(\sigma_D^#) = \psi_2(S^#[[Q^#]]\sigma_D^#)$. By following [11], we can prove the soundness, i.e.

$$ (\psi_2(\sigma_D^#) = \psi_2(S^#[[Q^#]]\sigma_D^#)) \implies \forall Q \in \gamma(Q^#), \forall \sigma_D \in \gamma(\sigma_D^#) : \psi_2(\sigma_D) = \psi_2(S[[Q]]\sigma_D) $$

where $\gamma$ is the concretization function [6].

There exist various relational and non-relational abstract domain in the abstract interpretation framework. The efficiency and preciseness of static analysis

<footnote n="4">⁴ Interested readers may refer [11] for more details on concrete and abstract semantics of query languages.</footnote>
vary depending on the abstract domain chosen [6]. As our objective is to con-
sider enterprise policies on database, we choose a relational abstract domain –
the domain of polyhedra [7] – to compute semantic relevancy of HQL code.

**Domain of Polyhedra.** Convex polyhedra are regions of some *n*-dimensional
space $\mathbb{R}^n$ that are bounded by a finite set of hyperplanes. Let $\vec{x} = \langle x_1, x_2, \dots, x_n \rangle$
and $\vec{v} = \langle v_1, v_2, \dots, v_n \rangle \in \mathbb{R}^n$ be the program variables of real numbers and an
*n*-tuple (vector) of real numbers. By $\beta = \vec{v} \cdot \vec{x} \otimes c$ where $\vec{v} \neq \vec{0}, c \in \mathbb{R}, \otimes \in \{=, \ge\}$,
we denote a set of linear restraints over $\mathbb{R}^n$. Given a set of linear restraints $\beta$ on
$\mathbb{R}^n$, a set of solutions or points $\{\sigma|\sigma \models \beta\}$ defines the polyhedron $P = (\beta, n)$. We
denote this set of points by $\gamma(P)$ [4,7].

Let $p$ be a set of all polyhedra on $\mathbb{R}^n$. We define a complete lattice $L_A =
\langle p, \sqsubseteq, \emptyset, \mathbb{R}^n, \sqcup, \sqcap \rangle$ where $\emptyset$ and $\mathbb{R}^n$ are bottom and top elements respectively.
Given $P_1, P_2 \in p: P_1 \sqsubseteq P_2 \Rightarrow \gamma(P_1) \subseteq \gamma(P_2)$, $P_1 \sqcap P_2 \Rightarrow \gamma(P_1) \cap \gamma(P_2)$ and $P_1 \sqcup P_2$
returns convex polyhedron hull which is the least polyhedron covering both
$P_1$ and $P_2$ [4]. Various operations of convex polyhedra are emptiness checking,
projection, etc [4].

Given a complete lattice L_C = ⟨Val, ⊑, ⊥, Val, ∪, ∩⟩ of the concrete do-
main of values Val, the correspondence between concrete and abstract domains
is formalized by Galois Connection ⟨L_C, α, γ, L_A⟩ where α and γ are abstraction
and concretization functions respectively [6].

**Abstract semantics.** The transition relation is defined as $\mathcal{T}: \mathbf{Com} \times \mathbf{p} \to \mathcal{P}(\mathbf{p})$ where $\mathbf{Com}$ is the set of commands and $\mathbf{p}$ is the set of all polyhedra. It defines the abstract semantics of a command in the domain of polyhedra by specifying how application of a command on a polyhedron results into a set of new polyhedra.

*Example 1. (Assignment)* Given P=(β, n)=(⟨x≥3, y≥2⟩, 2). The transition semantics of assignment statement x := x + y is defined as: 𝒯[⟨x := x + y⟩P = {P'}⟩ where P' = (⟨x - y ≥ 3, y ≥ 2⟩, 2).

*Example 2. (Test)* Given P= (β, n)= ({{x ≥ 4, y ≥ 3}}, 2). The transition semantics of boolean expression x ≥ 10 is defined as: 𝒯[ x ≥ 10 ] P = {PT, PF} where

$P_T = (\{ x \ge 10, y \ge 3 \}, 2)$ and $P_F = (\{ x \ge 4, -x \ge -9, y \ge 3 \}, 2)$.

We are now in position to define abstract transition semantics of Hibernate
Session methods. We denote the abstract syntax of Session methods by triplet
⟨C, φ, OP⟩ where OP is the operation to be performed on a set of tuples satisfying
φ in database tables corresponding to a set of classes C. The condition φ is a
first order logic formula. Four basic OP that cover a wide range of operations are
SAVE, UPD, DEL, and SEL [5].

- ⟨C, φ, SAVE(obj)⟩ = ⟨{c}, false, SAVE(obj)⟩: Stores the state of the object obj in the database table t, where t corresponds to the POJO class c and obj is the instance of c. The pre-condition φ is false as the method does not identify any existing tuples in the database.
- $\langle C, \phi, \text{UPD}(\vec{x}, e\vec{x}p) \rangle = \langle \{c\}, \phi, \text{UPD}(\vec{v}, e\vec{x}p) \rangle$: Updates the attributes corresponding to the class fields $\vec{x}$ by $e\vec{x}p$ in the database table $t$ for the tuples satisfying $\phi$, where $t$ corresponds to the POJO class $c$.

- $\langle C, \phi, \text{DEL}(\cdot) \rangle = \langle \{c\}, \phi, \text{DEL}(\cdot) \rangle$: Deletes the tuples satisfying $\phi$ in $t$, where $t$ is the database table corresponding to the POJO class $c$.

- $\langle C, \phi, \text{SEL}(f(e\vec{x}p'), r(h(\vec{x})), \phi', g(e\vec{x}p)) \rangle$: Selects information from the database tables corresponding to the set of POJO classes C, and returns the equivalent representations in the form of objects. This is done only for the tuples satisfying $\phi$. As of [11], we denote by $g, h, r, f, \phi'$ the GROUP BY, Aggregate Functions, DISTINCT/ALL, ORDER BY, and HAVING clause respectively.

Observe that as `SAVE()`, `UPD()` and `DEL()` always target single class, the set C is a singleton {$c$}. However, C may not be singleton in case of `SEL()`.

As there is a correspondence between HQL variables and database attributes, we define the transition semantics $\mathcal{T}_{\text{hql}}$ ofHibernate Session methods in terms of the transition semantics $\mathcal{T}_{\text{sql}}$ in the corresponding database domain as follows:

$$ \mathcal{T}_{\text{hql}}[\langle C, \phi, \text{OP} \rangle] = \begin{cases} \mathcal{T}_{\text{sql}}[\langle T, \phi_d, \text{OP}_d \rangle] & \text{if } C = \{c_1, \dots, c_n\} \wedge (\forall i \in 1 \dots n. t_i = \text{Map}(c_i)) \wedge T = \{t_1, t_2, \dots, t_n\}. \\ \perp & \text{otherwise.} \end{cases} $$

`Map()` is a function which maps any HQL component into an equivalent database component involving only database tables and attributes. Thus, $\phi_d = \text{Map}(\phi)$, $\text{OP}_d = \text{Map}(\text{OP})$ are the condition-part (WHERE clause) and the database operations (`UPDATE`, `DELETE`, `INSERT`, `SELECT`) defined on the underlying database.

**Example 3.** Consider Figure 3 and the following Session method:

$$ m_{\text{upd}} ::= \text{ses}\cdot\text{CreateQuery}(\text{UPDATE } \text{cls}\text{ SET } sal = sal+100 \text{ WHERE } age \ge 30)\cdot\text{executeUpdate()} $$

The equivalent abstract syntax is $\langle \{\text{cls}\}, age \ge 30, \text{UPD}(\langle sal \rangle, \langle sal + 100 \rangle) \rangle$. The function `Map(m\_upd)` converts $m\_upd$ into an equivalent database operation whose abstract syntax is $\langle \{\text{Tab}\}, age \ge 30, \text{UPDATE}(\langle tsal \rangle, \langle tsal + 100 \rangle) \rangle$ where

$$ \begin{aligned} \text{Map}(\{\text{cls}\}) &= \{\text{Tab}\}, & \text{Map}(\text{age} \ge 30) &= \text{age} \ge 30, \\ \text{Map}(\text{UPD}(\langle sal \rangle, \langle sal + 100 \rangle)) &= \text{UPDATE}(\langle tsal \rangle, \langle tsal + 100 \rangle) \end{aligned} $$

Let us define abstract transition semantics of four different database operations corresponding to the four aforementioned Session methods in the domain of polyhedra.

1. Update:

$$ \mathcal{T}_{\text{hql}}[\langle \{c\}, \phi, \text{UPDATE}(\vec{x}, e\vec{x}p) \rangle] \mathcal{P} = \mathcal{T}_{\text{sql}}[\langle \{t\}, \phi_d, \text{UPDATE}(\vec{x}_d, e\vec{x}_p) \rangle] \mathcal{P} = \{P'_T, P_F\} $$

where

$$ P_T = (P \sqcap \phi_d). $$

$$ P'_T = \mathcal{T}_{\text{sql}}[\text{UPDATE}(\vec{x}_d, e\vec{x}_p)] P_T = \mathcal{T}_{\text{sql}}[\vec{x}_d := e\vec{x}_p] P_T. $$

$$ P_F = (P \sqcap \neg \phi_d). $$
By the notation $\vec{x}_d := \exp p_d$ we denote $\langle x_1 := \exp_1, x_2 := \exp_2, \dots, x_n := \exp_n \rangle$ where $\vec{x}_d = \langle x_1, x_2, \dots, x_n \rangle$ and $\exp p_d = \langle \exp_1, \exp_2, \dots, \exp_n \rangle$, which follow transition semantic definition for assignment statement.

Example 4. Consider table Tab in Figure 3(a). The abstract representation of Tab in the form of polyhedron is:

$$P = \langle \{teid \ge 1, -teid \ge -4, tsal \ge 800, -tsal \ge -2000, tage \ge 18, -tage \ge -62\}, 3 \rangle$$

Consider the following Session method defined on class Cls:

$$m_{upp} ::= ses.CreateQuery(UPDATE Cls SET sal = sal+100 WHERE age \ge 30).executeUpdate().$$

The equivalent abstract syntax is $\langle \{\text{Cls}\}, \text{age} \ge 30, \text{UPD}(\langle \text{sal} \rangle, \langle \text{sal} + 100 \rangle) \rangle$. The abstract transition semantics of $m_{upp}$ on P is:

$$ \begin{aligned} \mathcal{T}_{hql}[[m_{upp}]]P &= \mathcal{T}_{hql}[[\langle \{\text{Cls}\}, \text{age} \ge 30, \text{UPD}(\langle \text{sal} \rangle, \langle \text{sal} + 100 \rangle) \rangle]]P \\ &= \mathcal{T}_{sql}[[\langle \{\text{Tab}\}, \text{tage} \ge 30, \text{UPDATE}(\langle \text{tsal} \rangle, \langle \text{tsal} + 100 \rangle) \rangle]]P = \{P'_T, P_F\} \text{ where} \end{aligned} $$

$$P'_T = \langle \{teid \ge 1, -teid \ge -4, tsal \ge 900, -tsal \ge -2100, tage \ge 30, -tage \ge -62\}, 3 \rangle.$$

$$P_F = \langle \{teid \ge 1, -teid \ge -4, tsal \ge 800, -tsal \ge -2000, tage \ge 18, -tage \ge -29\}, 3 \rangle.$$

2. Delete: $\mathcal{T}_{sql}[[\langle t \rangle, \phi_d, \text{DELETE}(t)]]]P = \{(P \sqcap \neg \phi_d)\}$

Example 5. Consider the following Session method:

$$m_{del} ::= ses.CreateQuery(DELETE from Cls WHERE age \ge 30).executeUpdate().$$

The transition semantics of $m_{del}$ on P is:

$$ \begin{aligned} \mathcal{T}_{hql}[[m_{del}]]P &= \mathcal{T}_{hql}[[\langle \{\text{Cls}\}, \text{age} \ge 30, \text{DEL}(t) \rangle]]P \\ &= \mathcal{T}_{sql}[[\langle \{\text{Tab}\}, \text{tage} \ge 30, \text{DELETE}(t) \rangle]]P \\ &= \{P \sqcap \neg (\text{tage} \ge 30)\} = \{P'\} \text{ where} \end{aligned} $$

$$P' = \langle \{teid \ge 1, -teid \ge -4, tsal \ge 800, -tsal \ge -2000, tage \ge 18, -tage \ge -29\}, 3 \rangle$$

3. Insert: Let $\vec{x}$ be the fields of a class c. Given an object obj of c, suppose $\vec{v}$ be the values in $\vec{x}$ of the object. The transition relation is defined as

$$ \mathcal{T}_{hql}[[\langle \{c\}, \text{false, SAVE(obj)} \rangle]]P = \mathcal{T}_{sql}[[\langle \{t\}, \text{false, INSERT attribute(t), \vec{v}} \rangle]]P = \{P'\} $$

$$\text{where } P' = P \sqcup \{\text{attribute}(t) = \vec{v} \mid \vec{v} \in \mathbb{R}^n\}.$$

Example 6. Let obj be an object of POJO class Cls in Figure 3 whose fields $\vec{x} = \langle eid, sal, age \rangle$ are set to values $\vec{v} = \langle 5, 600, 35 \rangle$. Consider the following Session method $m_{ins} ::= ses.save(obj)$. The transition semantics is:

$$ \begin{aligned} \mathcal{T}_{hql}[[m_{ins}]]P &= \mathcal{T}_{hql}[[\langle \{\text{Cls}\}, \text{false, SAVE(obj)} \rangle]]P \\ &= \mathcal{T}_{sql}[[\langle \{\text{Tab}\}, \text{false, INSERT}(\langle \text{teid}, \text{tsal}, \text{tage} \rangle, \langle 5, 600, 35 \rangle) \rangle]]P = \{P'\} \end{aligned} $$

$$\text{where } P' = P \sqcup \{teid = 5, tsal = 600, tage = 35\} = \langle \{teid \ge 1, -teid \ge -5, tsal \ge 600, -tsal \ge -2000, tage \ge 18, -tage \ge -62\}, 3 \rangle$$
<figure><img src="image_4.png" /><figcaption>Fig. 4: Syntax-based Slice w.r.t. $\psi_1$.</figcaption></figure>

**4. Select:** The select operation does not modify any information in a polyhedron. Therefore, the transition relation is defined as:

$$ \mathcal{T}_{sql}[[T, \phi_d, \text{SELECT}(f(\vec{exp}'_d), r(\vec{h}(\vec{x}_d))), \phi'_d, g(\vec{ex}p'_d))]P = \{P\} $$

## 5 Illustration on the running example

Let us illustrate our proposed approach on the running example (Figure 1) in section 2.

**Syntax-based Slicing.** The backward slice of Prog w.r.t. $\psi_1$ is depicted in Figure 4. This is done by traversing the syntax-based dependence graph (Figure 2) in backward direction w.r.t. the slicing criteria $\langle 21, \{sal, age, maxsl\} \rangle$. Observe that the sliced-database on which the slice performs its computation, is a part of the original database. This has crucial role in data-provenance applications.

**Semantic-based Slicing.** The initial polyhedron<fnref n="5" /> corresponding to the database dB (Figure 1(b)) is $P_{dB} = \langle\{teid \ge 1, -teid \ge -5, tsal \ge 600, -tsal \ge -2500, tage \ge 20, -tage \ge -45\}, 3\rangle$. The pictorial representation is shown in Figure 5(a).

The abstract syntax of Session methods $m_{sel}$, $m_{upd}$ and $m_{del}$ at program points 10, 16, 19 respectively in Prog are:

$$ m_{sel} ::= \langle C, \phi, OP \rangle \text{ where } C = \{\text{emp}, \text{Job}\}, \phi = \{\text{eid} = \text{jobid}, \text{eid} = \text{id}_v\}, \\ OP = \text{SEL}(f(\vec{ex}p'), r(\vec{h}(\vec{x})), \phi', g(\vec{ex}p)) = \text{SEL}(\text{id}, \text{ALL}(\text{id}(\text{jname})), \text{true}, \text{id}), \\ \text{and } \text{id} \text{ denotes identity function.} $$

$$ m_{upd} ::= \langle \{\text{emp}\}, \{\text{eid} = \text{id}_v\}, \text{UPD}(\langle \text{sal} \rangle, \langle \text{sal} + \text{sal}_v \rangle) \rangle $$

$$ m_{del} ::= \langle \{\text{emp}\}, \{\text{eid} = \text{id}_v\}, \text{DEL}(\rangle) $$

The transition semantics on $P_{dB}$ are:

<footnote n="5">⁵ For the sake of simplicity, we consider the polyhedron in the space involving only three attributes teid, tsal and tage.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 5: Polyhedra representation of temp on various operation (m$_{sel}$,m$_{udp}$,m$_{del}$).</figcaption></figure>

$$
\begin{align*}
\mathcal{T}_{\text{hql}}[\mathbf{m}_{\text{sel}}]\mathbf{P}_{\text{dB}} \\
&= \mathcal{T}_{\text{hql}}[\langle\{\text{emp}, \text{Job}\}, \{\text{eid} = \text{jobid}, \text{eid} = \text{id\_v}\}, \text{SEL}(\text{id}, \text{ALL}(\text{id}(\text{jname})), \text{true}, \text{id})\rangle]\mathbf{P}_{\text{dB}} \\
&= \mathcal{T}_{\text{sql}}[\langle\{\text{temp}, \text{tjob}\}, \{\text{teid} = \text{tjobid}, \text{teid} = \text{tid\_v}\}, \text{SELECT}(\text{id}, \text{ALL}(\text{id}(\text{tjname})), \text{true}, \text{id})\rangle]\mathbf{P}_{\text{dB}} \\
&= \{\mathbf{P}_{\text{dB}}\}
\end{align*}
$$

Note that, select operation does not change the database, hence the polyhedron
remains unchanged (see Figure 5(b)).

$$
\begin{align*}
\mathcal{T}_{\text{hql}}[\mathbf{m}_{\text{upd}}] &= \mathcal{T}_{\text{hql}}[\langle\{\text{emp}\}, \{\text{eid} \ge \text{id\_v}\}, \text{UPD}(\langle\text{sal}\rangle, \langle\text{sal} + \text{sal\_v}\rangle)\rangle]\mathbf{P}_{\text{dB}} \\
&= \mathcal{T}_{\text{sql}}[\langle\{\text{temp}\}, \{\text{teid} \ge \text{id\_v}\}, \text{UPDATE}(\langle\text{tsal}\rangle, \langle\text{tsal} + \text{sal\_v}\rangle)\rangle]\mathbf{P}_{\text{dB}} \\
&= \{\mathbf{P}'_T, \mathbf{P}_F\} \quad \text{where}
\end{align*}
$$

$$
P_T = P_{dB} \cap \{teid \geq id_v\}
$$

$$
\begin{align*}
P'_{T} &= \mathcal{T}_{\text{sql}}[\text{tsal} := \text{tsal} + \text{sal\_v}](P_{T}) \\
&= \langle\{\text{teid} \ge 1, -\text{teid} \ge -5, \text{tage} \ge 20, -\text{tage} \ge -45, \text{tsal} \ge 600\}, 3\rangle.
\end{align*}
$$

$$
P_F = \{ \mathbf{P}_{dB} \sqcap \neg(\mathit{teid} \ge \mathit{id\_v}) \} = \{ \mathbf{P}_{dB} \}
$$

Note that, since the updation of tsal depends on run-time input, we project-
out the upper bound of the attribute from the set of restraints in P'_{T} in order
to guarantee the soundness. The polyhedron representation of P'_{T} is shown in
Figure 5(c). Also note that, P_{F} is sound-approximated by disregarding the effect
of "teid = id\_v" as it depends on run-time input.

$$
\begin{align*}
\mathcal{T}_{\text{hql}}[\mathbf{m}_{\text{del}}] &= \mathcal{T}_{\text{hql}}[\langle\{\text{emp}\}, \{\text{eid} = \text{id\_v}\}, \text{DEL}(\text{ })\rangle\mathbf{P}_{\text{dB}} \\
&= \mathcal{T}_{\text{sql}}[\langle\{\text{temp}\}, \{\text{teid} = \text{id\_v}\}, \text{DELETE}(\text{ })\rangle\mathbf{P}_{\text{dB}} = \{\mathbf{P}_{\text{dB}}\}
\end{align*}
$$
Note that, the semantics of $m_{del}$ is sound-approximated by disregarding the effect of "teid = id_v" as it depends on run-time input (see Figure 5(d)).

<figure><img src="image_6.png" /><figcaption>Fig. 6: Semantics-based slice of Prog w.r.t $\psi_1$</figcaption></figure>

Observe that the initial polyhedron of dB is covered by the polyhedron representing $\psi_1$. This can be verified by performing the operations, e.g. interaction, emptiness checking, etc. on the polyhedra domain. Therefore, initially $\psi_1$ is satisfied by dB. The abstract semantics-based analysis proves that $m_{del}$ does not change the initial polyhedron $P_{dB}$ (see Figure 5). Therefore it is semantically irrelevant w.r.t. $\psi_1$. The semantics-based slice is shown in Figure 6 which disregards the semantically irrelevant statements w.r.t. $\psi_1$, yielding to a slice more accurate than the syntax-based one (Figure 4).

## 6 Conclusion

In this paper, we introduce a policy-based slicing ofHibernate Query Language where the policies are defined on persistent objects, rather than transient objects. We extend the Class Dependence Graph (CIDG) [16] of object-oriented languages to the case of HQL, and propose a refinement of dependence graph for removing false dependences by analyzing programs in relational or non-relational abstract domains by following the Abstract Interpretation framework.

Our approach is comparable with conditioned slicing and specification-based slicing (several variants exist, e.g. precondition-, postcondition-, contract-, assertion-based, etc.) [3]. The method defined for finding a conditioned slice is to use symbolic execution and reject infeasible paths based on the constraints defined by the first order logic equations. Specification-based slicing approach is proposed based on the axiomatic semantics (weakest precondition or strongest postcondition computations) in program verification. All these approaches use SMT solver which has exponential complexity [15]. Our proposal is based on the semantic analysis in an abstract domain following the Abstract Interpretation framework. The framework allows to perform analysis in a relational or non-relational abstract domain based on the properties of interest. Analysis in the domain of polyhedra uses Linear Problem Solver [1]. Although in some cases the worst-case computational complexity in polyhedron domain is exponential [14, 18], but there is an opportunity to choose another less costlier weakly relational domains such as the domain of octagons [19].
References

1. Bagnara, R., Hill, P.M., Zaffanella, E.: The ppl: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Tech. rep., Dipartimento di Matematica, Università di Parma, Italy (2006)

2. Bauer, C., King, G.:Hibernate in Action. Manning Publications Co. (2004)

3. Canfora, G., Cimitile, A., Lucia, A.D.: Conditioned program slicing. Information and Software Technology 40(11–12), 595–607 (1998)

4. Chen, L., Minè, A., Cousot, P.: A sound floating-point polyhedra abstract domain. In: Proc. of the 6th Asian Symposium on PLS. pp. 3–18 (2008)

5. Cortesi, A., Halder, R.: Information flow analysis of hibernate query language. In: Proc. of the 1st Int. Conf. on FDSE. pp. 262–274 (2014)

6. Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Proc. of the POPL’77. pp. 238–252 (1977)

7. Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: Proceedings of the POPL ’78. pp. 84–96 (1978)

8. Glass, R.L.: It failure rates-70% or 10-15%? IEEE Software 22(3), 112–111 (2005)

9. Gyimóthy, T., Paakki, J.: Static slicing of logic programs. In: Automated and Algorithmic Debugging. pp. 87–103 (1995)

10. Halder, R., Cortesi, A.: Abstract program slicing of database query languages. In: Proc. of the 28th Annual ACM SAC. pp. 838–845 (2013)

11. Halder, R., Cortesi, A.: Abstract interpretation of database query languages. Computer Languages, Systems & Structures 38, 123–157 (2012)

12. Halder, R., Cortesi, A.: Abstract program slicing on dependence condition graphs. Sci. Comput. Program. 78(9), 1240–1263 (2013)

13. Horwitz, S., Reps, T., Binkley, D.: Interprocedural slicing using dependence graphs. ACM Transactions on PLS 12(1), 26–60 (1990)

14. Kelner, J.A., Spielman, D.A.: A randomized polynomial-time simplex algorithm for linear programming. In: Proc. of the Theory of Computing. pp. 51–60 (2006)

15. King, T., Barrett, C., Tinelli, C.: Leveraging linear and mixed integer programming for smt. In: Proc. of the 14th ICFMCAD (2014), lausanne, Switzerland, to appear

16. Larsen, L., Harrold, M.J.: Slicing object-oriented software. In: Proc. of the 18th ICSE. pp. 495–505 (1996)

17. Mastroeni, I., Zanardini, D.: Data dependencies and program slicing: from syntax to abstract semantics. In: Proc. of the ACM symposium on PEPM. pp. 125–134 (2008)

18. Megiddo, N.: Linear programming in linear time when the dimension is fixed. Journal of the ACM 31(1), 114–127 (1984)

19. Minè, A.: The octagon abstract domain. Higher Order Symbol. Comput. 19(1), 31–100 (2006 http://wwwastreeensfr/)

20. Ottenstein, K.J., Ottenstein, L.M.: The program dependence graph in a software development environment. ACM SIGPLAN Notices 19(5), 177–184 (1984)

21. Podgurski, A., Clarke, L.A.: A formal model of program dependences and its implications for software testing, debugging, and maintenance. IEEE Transactions on Software Engineering 16(9), 965–979 (1990)

22. Rodrigues, N.F., Barbosa, L.S.: Slicing functional programs by calculation. In: Beyond Program Slicing, 06.11. - 11.11.2005 (2005)

23. Tip, F.: A survey of program slicing techniques. Tech. rep. (1994)

24. Weiser, M.: Program slicing. IEEE Trans. on SE SE-10(4), 352–357 (1984)

25. Willmor, D., Embury, S.M., Shao, J.: Program slicing in the presence of a database state. In: Proc. of the 20th Int. Conf. on Software Maintenance. pp. 448–452 (2004)