The analysis of phone recordings is one of the activities typically performed in the Digital Forensics practice. It provides information such as the geographical position of some suspect, useful to reconstruct the network of contacts. In this work we have considered the problem of analyzing a dataset of anonymized phone recordings made available within the DigForASP project by looking for sequential patterns in the recordings. The approach followed leverages the expressive and inferential power of the Answer Set Programming paradigm. The experiments reported here concern the extraction of closed and maximal patterns (condensed representations), which significantly reduces the number of returned patterns without loss of information.
disruptive innovations in the forensic practice [1, 2]. The ultimate goal of Evidence Analysis is indeed the formulation of verifiable evidence that can be rationally presented in a trial. Under this perspective, the results provided by, e.g., ML classifiers or other types of “black box” AI systems can be regarded as having the same value as human witness’ suspicions. Therefore, they could not be used as legal evidence. Conversely, logic-based AI methods provide a broad range of proof-based reasoning functionalities that can be implemented in a declarative framework where the problem specification and the computational program are closely aligned. This has the benefit that the correctness of the resulting systems can be formally verified. Moreover, new methods for visualising and explaining the computed answers (e.g., based on graphical languages) have been recently proposed. So one can not only model and solve relevant problems, but also efectively communicate the conclusions (and their proofs) in a transparent, comprehensible and justified way. This approach is the one adopted by the COST Action “Digital forensics: evidence analysis via intelligent systems and practices" (DigForASP)1, a large international cooperation network which aims at promoting formal and verifiable AI methods and techniques for Evidence Analysis [3].
A typical DF problem is the analysis of phone recordings. Indeed, during the investigation of a crime, it is common to analyze the communications of a particular suspect. Since nowadays mobile phones are objects owned by anyone, it can be useful for investigators to analyze the calls or messages exchanged. The telephone records contain all the traces of communications (calls, SMS, and all the data trafic) concerning a specific user over a certain period of time. Note that phone records do not trace important data such as the audio of calls sent or received. In fact, they only provide a trace of the communication that has taken place but not its content. The phone records can be requested by the Judicial Authority if deemed useful in order to carry out investigations involving the individual owner of the phone. Correctly analyzing the telephone records is essential to obtain useful hints. Depending on the analysis, diferent types of information can be extracted. The records are typically analyzed for comparing the geographical positions with respect to the declarations, and for reconstructing the network of contacts of a single user in order to trace which conversations (s)he has had with whom, where and when. In this paper we consider the problem of mining sequences in phone recordings in order to discover frequent sequential patterns. In particular, we propose a declarative approach based on Answer Set Programming (ASP) which adapts previous work in sequential pattern mining [4, 5] to the problem in hand. The proposed approach is in the spirit of DigForASP and appears a promising support to the analysis of events and sequences of events in scenarios of interest to DF experts. This paper extends the preliminary work reported in [6] with a significant refinement aimed at addressing some limits of pattern mining such as the size of the output. In particular, here we explore the use of condensed representations for sequential patterns.
The paper is organized as follows. In Section 2 we provide the necessary preliminaries on ASP and sequential pattern mining. In Section 3 we describe the specific case study for the analysis of mobile phone recordings. In Section 4 we report the details of our ASP-based approach, including the ASP encodings, and the experimental results obtained by comparing the behaviour of the encodings. In Section 5 we conclude by commenting the ongoing work and by outlining some promising directions for research.
In the following we give a brief overview of the syntax and semantics of disjunctive logic programs in ASP. The reader can refer to, e.g, [7] for a more extensive introduction to ASP.
Let be a fixed countable set of (domain) elements, also called constants, upon which a total order ≺ is defined. An atom is an expression (1, . . . , ), where is a predicate of arity ≥ 0 and each is either a variable or an element from (i.e, the resulting language is function-free). An atom is ground if it is free of variables. We denote the set of all ground atoms over by . A (disjunctive) rule is of the form
1 ∨ . . . ∨ ← 1, . . . , , +1, . . . , with ≥ 0, ≥ ≥ 0, + > 0, where 1, . . . , , 1, . . . , are atoms, or a count expression of the form #{ : 1, . . . , } ◁▷ , where is an atom and is a literal (i.e, an atom which can be negated or not), 1 ≥ ≥ , ◁▷∈ {≤ , <, =, >, ≥} , and ∈ N. Moreover, “not” denotes default negation. The head of is the set ℎ() = {1, . . . , } and the body of is () = {1, . . . , , +1, . . . , }. Furthermore, we distinguish between +() = {1, . . . , } and − () = {+1, . . . , }. A rule is normal if ≤ 1 and a constraint if = 0. A rule is safe if each variable in occurs in +(). A rule is ground if no variable occurs in . A fact is a ground rule with () = ∅ and |ℎ()| = 1. An (input) database is a set of facts. A program is a finite set of rules. For a program Π and an input database , we often write Π( ) instead of ∪ Π . If each rule in a program is normal (resp. ground), we call the program normal (resp. ground).
Given a program Π , let Π be the set of all constants appearing in Π . (Π) is the set of rules obtained by applying, to each rule ∈ Π , all possible substitutions from the variables in to elements of Π. For count-expressions, { : 1, . . . , } denotes the set of all ground instantiations of , governed through 1, . . . , . An interpretation ⊆ satisfies a ground rule if ℎ() ∩ ̸= ∅ whenever +() ⊆ , − () ∩ = ∅, and for each contained count-expression, ◁▷ holds, where = |{|1, . . . , }|, ∈ N and ◁▷∈ {≤ , <, =, >, ≥} . A ground program Π is satisfied by , if satisfies each ∈ Π . A non-ground rule (resp., a program Π ) is satisfied by an interpretation if satisfies all groundings of (resp., (Π) ). A subset-minimal set ⊆ satisfying the Gelfond-Lifschitz reduct Π = {ℎ() ← +()| ∩ − () = ∅, ∈ (Π) } is called an answer set of Π . We denote the set of answer sets for a program Π by (Π) .
The tools used in this work are part of the Potassco2 collection [8]. The main tool of the collection is the clingo ASP solver [9].
Our terminology on sequence mining follows the one in [10]. Throughout this article, [] = {1, . . . , } denotes the set of the first positive integers.
Let Σ be the alphabet, i.e, the set of items. An itemset = {1, 2, . . . , } ⊆ Σ is a finite
set of items. The size of , denoted ||, is . A sequence is of the form = ⟨12 . . . ⟩
where each is an itemset, and is the length of the sequence. A database is a multiset
of sequences over Σ . A sequence = ⟨1 . . . ⟩ with ∈ Σ is contained in a sequence
= ⟨1 . . . ⟩ with ≤ , written ⊑ , if ⊆ for 1 ≤ ≤ and an increasing sequence
(1 . . . ) of positive integers ∈ [], called an embedding of in . For example, we have
⟨()⟩ ⊑ ⟨()⟩ relative to embedding (
Given a database , the cover of a sequence is the set of sequences in that contain : (, ) = { ∈ | ⊑ }. The number of sequences in containing is called its support, that is, (, ) = |(, )|. For an integer ℎ, the problem of frequent sequence mining is about discovering all sequences such that (, ) ≥ ℎ. We often call a (sequential) pattern, and ℎ is also referred to as the (minimum) support threshold. For ℎ = 2 we can see how ⟨⟩, ⟨⟩, ⟨⟩, ⟨ ⟩, ⟨ ⟩, ⟨ ⟩ and ⟨ ⟩ are common patterns in the database reported in Table 1.
The ASP encoding for sequential pattern mining considered in this paper follows the principles outlined in [11] and [4]. In particular, is represented as a collection of ASP facts seq(t, p, e), where the seq predicate says that an item e occurs at position p in a sequence t. Also, there are two parameters to be defined. Besides th, maxlen determines the maximum pattern length. The lower the value of th the more patterns will be extracted; the lower the value of maxlen, the smaller the ground program will be. Therefore the parameters allow a tuning for the program eficiency. Finally, each answer set comprises a single pattern of interest. More precisely, an answer set represents a frequent pattern = ⟨⟩≤ ℎ≤ such that 1 ≤ ≤ from atoms (1, 1), ..., (, ). The first argument expresses the position of the object in increasing order, where m can vary, while 1 always indicates the first item in the pattern. For example the atoms pat(1, a), pat(2, b) and pat(3, c) describe a frequent pattern ⟨ ⟩ of the database in Table 1.
For a thorough discussion of the program the reader can refer to [5].
As a case study for our application of sequential pattern mining in DF, we have considered a dataset that has been made available by Prof. David Billard (University of Applied Sciences in Geneva) under NDA to DigForASP members for academic experimentation. In the following we provide details of the structure of the dataset and of the pre-processing which is necessary in order to put the dataset into a more suitable format for the application in hand.
The dataset consists of the telephone records of four users from a real-word investigative case. Each file in the dataset has the following schema: • Type: what kind of operation the user has performed (e.g, incoming/outgoing call or
SMS); • Caller: who makes the call or sends an SMS; • Callee: who receives the call or SMS; • Street: where the operation has taken place; • Time: when the operation has taken place (ISO format3 HH: MM: SS); • Duration: how long the operation has been (ISO format HH: MM: SS); • Date: when the operation has taken place (format: day, month, year).
The type of the operation is one of the following cases: “config”, “gprs”, “redirect”, “out_sms(SUB_TYPE)”, “in_sms(SUB_TYPE)”, “out_call(SUB_TYPE)”, “in_call(SUB_TYPE)”. Subtypes are: “simple”, “ack”, “foreign”.
The dataset has undergone the mandatory anonymization process for reasons of privacy and
confidentiality. Therefore it does not contain data that allows tracing back to the real people
involved in the investigative case. For instance, there is no phone number for the caller/callee
but only a fictitious name. The names and the sizes (# rows) of the four files in the dataset are
the following: Eudokia Makrembolitissa (
The DigForASP dataset in its original format can not be considered as a set of sequences. Therefore, it must undergo an intermediate transformation. In short, each line of the original dataset is transformed into an ASP fact through the seq_event atom.
The procedure for transforming the original dataset into sequences of ASP facts is the
following. Each row of the dataset has been transformed into a fact seq_event(t, p, e) (Listing 1),
where e represents the item (in our case the event), p defines the position of e within the
sequence t (identified by date). The term p is important as it allows you to define the order
of events within a sequence. More specifically, e is made up of the following features: Type,
Caller, Callee, Street_a and Street_b for the geo-location of the event, the (hour, minute, seconds)
3Format to describe dates and times: https://en.wikipedia.org/wiki/ISO_8601
triple, Weekday with range (0 = Monday, ..., 6 = Sunday), and Duration expressed in seconds.
Notice that, with reference to the first two facts in Listing 1, the event 1 is prior to 2 since
(1 = 1) < (2 = 2). Also, it is possible to transform in sequence only certain days, months
or years, so that the analysis can be carried out at diferent granularity levels.
seq_event((
Listing 1: Some facts representing sequences of events in the DigForASP dataset.
Additional pre-processing is required to create simpler and easier to analyze sequences out
of the seq_event atoms in Listing 1. The idea is to create sequences whose identifier refers to a
particular day describing what events on that day happened. For instance, in communication
sequences the event e refers to the (Caller, Callee) pair as shown in Listing 2.
seq((
For the purposes of law enforcement investigations, it is especially useful to understand what the extracted patterns are and what information they provide to the analyst. To this aim, we have modified the basic algorithm provided by [ 5] in such a way as to elaborate patterns whose items have a more complex structure, more precisely the structure of the DigForASP dataset (see Section 3.2). In Section 4.1, for the sake of self-containment of this paper, we briefly describe the base ASP encoding already presented in [6]. Then we introduce the ASP encoding for mining so-called condensed representations (closed and maximal patterns) in Section 4.2, and finally report the results of a comparative evaluation in Section 4.3.
Listing 3 reports the base version of our adaptation of [5] to the problem first introduced in [ 6] of mining communication sequences. Here, we need to handle items with an internal structure (Lines 1, 11, and 13). Also, it is necessary to figure out in which and in how many daily sequences the patterns are found (Line 21). Patterns are then enriched with additional information such as the type of operation (Type) carried out between the two communicating entities (CC) and the precise time of day (Time) with the relative date (T ) (Line 22). Furthermore, since the dataset contains rows with undefined values (indicated with none), two constraints have been added to eliminate all patterns with none (Lines 25-26). Finally, in addition to the maxlen parameter, often used in pattern mining, the minlen parameter has been introduced with relative constraint to filter out patterns not suficiently long (Line 29).
Each answer set returned by Listing 3 is a sequential pattern represented by means of the /2 predicate. As an example, Listing 4 reports the first answer out of the 15 generated by Listing 3 for a run over 100 instances from the DigForASP dataset, with maximum pattern length equal to 3 and minimum support threshold equal to 25%. It represents the sequential pattern which consists of two communication events: The first is between Margaret Hasse and Karen Cook McNally (Line 2), while the second is between Karen Cook McNally and Lucie Julia (Line 3). The pattern occurs in the days 8, 9 and 12 of September 2040 (see Line 4), and can be graphically presented as shown in Figure 1.
One of the major problems in pattern mining is still the problem of pattern explosion, i.e., the large amounts of patterns produced by the mining algorithms when analyzing a database with a predefined minimum support threshold. To address this issue, condensed representations for patterns have been proposed in the literature [rif ?].
In this Section we will discuss how additional requirements can be encoded with ASP in order to extract maximal and closed sequential patterns as shown in [5]. Let be a sequence database, (, ) the support evaluation function, and ℎ the minimum support threshold. A pattern is maximal, if there are no other patterns such that ⊆ and (, ) ≥ ℎ. A pattern is closed, if no other pattern exists such that ⊆ and (, ) = (, ). 1 % embeddings in a reverse order 2 rocc(T,L,P) :- seq(T,P,I), pat(L,I), patlen(L). 3 rocc(T,L,P) :- rocc(T, L, P+1), seq(T,P,_). 4 rocc(T,L,P) :- rocc(T, L+1, P+1), seq(T,P,C), pat(L,C). 5 6 % insertable items 7 ins(T,1 ,I) :- seq(T,P,I), rocc(T,1, P+1). 8 ins(T,L+1,I) :- seq(T,P,I), occ(T,L,P-1), patlen(L). 9 ins(T,X, I) :- seq(T,P,I), rocc(T,X,P+1), 10 occ(T,X-1,P-1), patpos(X), X>1. 11 12 % Integrity constraint for maximal patterns 13 :- item(I), X = 1..maxlen+1, { ins(T,X,I) : support(T) } >= th. 14 15 % Integrity constraint for closed patterns 16 :- item(I), X = 1..maxlen+1, { ins(T,X,I) } >=th, 17 ins(T,X,I) : support(T).
Listing 5 first describes how to define the set of items that can be inserted between successive items of an embedding (Lines 1-10). These itemsets are encoded by the atoms with predicate ins(T, X, I) where I is an item which can be inserted in an embedding of the current pattern in sequence T between items at position X and X+1 in the pattern. Here, only the positions of the last and the first valid occurrences are required for any pattern item. It can be observed that the strategy provides the first valid occurrence of an item X as the first atom of the occ(T, X, _) sequence. Then, computing the last occurrence for each pattern item can be done in a similar way by considering an embedding represented in reverse order. Lines 2 to 4 represent occ/3 and rocc/3 (reverse order) occurrences.
The computation of insertable items (Lines 7-10) exploits the above remark. Line 7 defines the insertable region in a prefix using rocc(T, 1, P). Since items are insertable if they are strictly before the first position, we consider the value of rocc(T, 1, P+1). Line 8 uses occ(T, L, P) to identify the sufix region. Lines 9-10 combine both constraints for in-between cases.
Listing 5 includes also the (integrity) constraints for dealing with closed and maximal patterns. To extract only maximal patterns, the constraint at Line 13 denies patterns for which it is possible to insert an item which will be frequent within sequences that support the current pattern. The constraint at Line 16 concerns the extraction of closed-patterns. It specifies that for each insertion position (from 1, in the prefix, to maxlen+1, in the sufix), it is not possible to have a frequent insertable item I for each supported transaction.
Though interesting from a theoretical point of view, these encodings lead to more complex programs and should be more dificult to ground and to solve as stressed in [5].
The goal of the experiments discussed in this Section is the comparative evaluation of the three versions of our ASP encoding for mining frequent, closed, and maximal sequential patterns, respectively. The comparison is done with respect to the number of patterns, the execution time and the memory usage, by varying the key parameters. The experiments can be grouped into two categories: 1. Discovery of frequent, closed and maximal patterns by varying: • the minimum support threshold from 10% to 50% while leaving the maximum pattern length fixed to 5; • the maximum pattern length (1, 3, 5 and 8) while leaving the minimum support threshold fixed to 25%.
• discovery of frequent patterns by varying the dataset size (100, 1K, 10K), while leaving the minimum support threshold unchanged (set to 25%) and the maximum pattern length fixed to 3.
All the experiments have been conducted over the largest available file of the DigForASP dataset (named Karen Cook McNally) made up of more than 20,000 instances. Given the size, a fairly long execution time for our ASP programs has been assumed. Therefore, the timeout has been set to 5 hours. As a solver, we have used the version 5.4.0 of clingo, with default solving parameters. The ASP programs were run on a laptop computer with Windows 10 (with Ubuntu 20.04.4 subsystem), AMD Ryzen 5 3500U @ 2.10 GHz, 8GB RAM without using the multi-threading mode of clingo. Multi-threading reduces the mean runtime but introduces variance due to the random allocation of tasks. Such variance is inconvenient for interpreting results with repeated executions.
In Table 2 and Figure 2 it is possible to observe how the use of condensed representations, in particular the maximal one, allows to reduce the number of extracted patterns. Considering the case of frequent patterns, the computation ends before the time limit only for the threshold set to 50%, while for the case of closed and maximal patterns the computation stopped at the time limit set at 5 hours. In the first case, the behavior is due to a more restrictive constraint, which allows to extract all the patterns in the dataset, while with a lower threshold values the patterns are many more. Viceversa, condensed representations require longer times to extract the patterns even at the same threshold values. As regards the memory usage (Table 2 and Figure 3), one can observe that it decreases, as the minimum support threshold decreases, and this holds for all condensed representations. In particular, the extraction of closed patterns uses more memory than the discovery of frequent and maximal patterns.
With a fixed threshold of 25% and the variation in the maximum pattern length (Table 3) we can see a generalized trend in which both the time taken and the memory used increase (Figure 5) as the length of the patterns increases. Notably, the memory usage is higher for closed patterns as already observed in the previous experiments. Except for the case of frequent patterns, the computation needed to extract patterns with a maximum length of 3 reaches the time limit. Once again, maximal patterns drastically reduce the size of the output (Figure 4).
For the scalability tests, values of 25% and 3 were chosen for the minimum support threshold and maximum pattern length, respectively. As can be seen in Table 4, the memory used increases as the size of the dataset increases (Figure 6). The time taken, except for frequent patterns, reaches the computation time limit for condensed representations when the size of the dataset is in the order of tens of thousands of rows (Figure 7). A general behavior concerns the closed patterns: The used memory is always higher than for the other representations in all the experiments done.
Pattern mining problems typically involve a combinatorial explosion. Condensed representations for patterns are among the solutions proposed in the literature to address this issue. In this paper we have reported the results of a comparative evaluation of the ASP encodings for solving three variants of the problem of mining sequential patterns, one being the base version (discovery of frequent patterns) and the other two using condensed representations ( discovery of closed and maximal patterns). As a case study we have considered the analysis of a real-world dataset of anonymised phone recordings. The results show that condensed representations have pros and cons. On one hand, they efectively reduce the number of patterns. On the other hand, they tend to consume more computational resources.
For the future we intend to consider the case of localization events, so that evidence can be analysed from a spatio-temporal viewpoint. Furthermore, we expect that the solicited feedback from the DF experts involved in DigForASP will not only validate our work but will also suggest new interesting directions of research.
This article is based upon work from COST Action 17124 “Digital forensics: evidence analysis via intelligent systems and practices (DigForASP)”, supported by COST (European Cooperation in Science and Technology). The work is also partially funded by the University of Bari “Aldo Moro” under the 2017-2018 grant “Metodi di Intelligenza Artificiale per l’Informatica Forense”. (A) Frequent