Underground forums are monitored platforms where hackers announce attacks and tools to carry on attacks on businesses or organizations. In this paper, we will experiment on assessing the risk of a dataset of these messages, using pattern structures and a lazy classification scheme, with some introduced complexity-reducing elements and natural language analysis techniques. The results show promising application for this method for this problem, and serve as an introductory step for deeper investigation.
Threat Intelligence constitutes a very critical part of the cybersecurity world nowadays, with
the intensifying cases of cyber attacks that are costing millions of dollars to many industries
and governments [
The practice of collecting information about attacks or ofers to attack a target from various
sources has attracted a lot of research and business attention. This is done by monitoring online
forums and instant messaging services, where threat actors post to let other members know
that they have some unauthorized access to a network, database or that they made a new tool
that can help to achieve the above goals. Most of the serious criminal activity is done for money
[
The forums consist of sub-forums and sections that deal with diferent topics and other administrative sections to control the announcement, sales, and membership processes. In addition to that, many forums have a direct marketplace section, where more strict rules about content are enforced and make these sections designated for sale/buying of illegal products, ranging from cracked software to confidential databases of entities.
The most prestigious forums also have an “escrow” service that works like a mediator between buyers and sellers on the forum and a type of guarantee of impartial control over the interaction. Many forums also have tiers of membership (VIP, Premium, Golden, etc.). Some forums have no free membership tiers, meaning that one have to pay to access their content. The content posted in paid sections or forums is supposed to have more credibility and be written by more interesting members, depending on the prices, which range from 10$ up to 300$. Most transactions are paid with cryptocurrency.
Detecting threats is usually performed with the help of human analysts. The analysts’ workflow has three main phases: discovery, reaction and analysis. The most time consuming and dificult to do is the first phase, where the analyst has to browse through thousands of messages posted daily to find credible threats to report. This is even harder when there is a constant stream of spam messages flooding the forums.
This work will focus on helping the human analysts in the discovery phase, using textual analysis of the messages, and learning approaches to help filter out the irrelevant messages, and tag all relevant messages with the right threat category to further ease the next two phases of the workflow.
Now to avoid confusion, we need to define some terms as they are mentioned in the system vs. how they are usually mentioned in the real world. Table 1 gives the terminology.
We need a system that can detect threats without capturing many false positive examples, or missing a true positive case, which carries a high business cost. Another constraint on the needed system is to be time sensitive, as many threats are very volatile, meaning that the threat actor will post about the sale of access for example, in several minutes or hours, some other criminal entity (or in some cases the victims) will contact him about the sale, pay him and request removing the sale announcement. The last important feature of the system is explainability, as human analysts need to understand the reasoning behind a classification result.
This will be achieved by building a learning-based system.
The rest of the paper is organized as follows: In Section 2 we recall basic denfiitions in formal concept analysis and pattern structures. In Section 3 we describe the lazy classification method using pattern structures. Section 4 describes the experimental setting. In Section 5, we discuss the preliminary results of applying the lazy classification to underground forum messages. We conclude the work in section 6.
Formal Concept Analysis (FCA) as defined in [
Let be a set of objects, a set of attributes or descriptions of these objects, and ⊆ × a binary relation between and . We call the triple (, ,) a formal context. If ∈ has the attribute ∈ , then (, ) ∈ . We then define the derivation operators (.)′ on ⊆ and ⊆ : ′ = { ∈ | ∀ ∈ : } ′ = { ∈ | ∀ ∈ : } (1) (2)
We call a pair (,) such that ′ = and ′ = , a formal concept, and is called its extent and is its intent. A partial order ≤ is defined on the set of concepts: ( ,) ≤ (C,D) if ⊆ and ⊆ . In this case, (,) is called the subconcept and (,) a superconcept. This partial order gives rise to a complete lattice on the set of all formal concepts. We call this the concept lattice of the formal context (, ,).
The hierarchical structure of concept lattices can be applied at mining association rules [
There is a large focus in FCA domain on building concept lattices and extracting the concepts
from a given formal context in an eficient manner, for it to become more applicable in the real
world [
To increase the applications of Formal Concept Analysis, it had to be able to represent more
complex data structures, like graphs or non-binary data. This need led to the development of
pattern structures [
Let be a set of objects and (, ⊓) be a meet-semi-lattice of possible object descriptions or patterns (for standard FCA, it would be the powerset of attribute set) with the similarity operator ⊓. Elements of are ordered by a subsumption relation ⊑ such that , ∈ , then one has ⊑ ⇔ ⊓ = . We also define : → as a mapping between objects and their attributes. We call (, , ) where = (, ⊓) a pattern structure. We can define the operators (· )◇ on ⊆ and ∈ (, ⊓) making Galois connection between the powerset of objects and ordered set of descriptions:
◇ = ⊓∈ () ◇ = { ∈ | ⊑ ()} (3) (4)
These operators will give us back the maximal set of patterns shared by the objects in and the maximal set of objects that share the description , respectively.
A pair (, ), ∈ and ∈ (, ⊓) that satisfies ◇ = and ◇ = is called a pattern concept, where is called the extent and is called the pattern intent of (, ).
A partial order ≤ is defined on the set of concepts: (, 1) ≤ (, 2) if ⊆ (or, equivalently, 2 ⊑ 1). This partial order forms a complete lattice on the set of all pattern concepts. We call this the pattern concept lattice of the pattern structure (, , ).
Pattern structures are helpful in applications with complex data, like graphs, many-valued
attributes [
For classification tasks we do not need to extract the full hidden knowledge from a dataset in
terms of implications, hypotheses or association rules, but a so-called lazy classification can be
applied [
In classification problems we have a target attribute, which, in the simplest case of two classes, has two values, denoted by + and − . By + we denote the set of objects that have the target attribute (positive examples) and by − we denote the set of objects that do not have the target attribute (negative examples), so that + ∩ − = ∅. Elements of that do not belong to any of these subsets are called unclassified examples .
A version of the lazy classification method [
This algorithm takes | | · ((⊓+ | | (⊑))) time, where (⊓), (⊑) are times for computing ⊓, ⊑, respectively.
Algorithm 1: Lazy Classification with Pattern Structures Requires: pattern structure (, , ), test example ∈ with description (), parameter 0 ≤ ≤ 1. 1: for ∈ + ∪ − : 2: compute sim = () ⊓ () 3: extsim = (sim)◇ 4: if % of objects in extsim have target attribute, classify positive 5: if % of objects in extsim do not have target attribute, classify negative 6: classify undetermined (the algorithm terminates without classification).
The examples dataset used in the following experiments is composed of underground forum messages as the objects and features extracted from these messages as attributes. After building the concept lattice from this dataset, we construct another dataset for testing the classification. Both datasets contain positive and negative examples. The target attribute is a simple flag stating whether the message is a real threat or not.
The procedure realizing the lazy classification scheme is as follows: we go through the objects of the formal context and check the extension of the intersection of the test object and the concept object, if all objects of this extension have the attribute value, then the test object is classified positively, if all of the objects of the extension do not have the attribute value, the test object is classified negatively, otherwise, the model cannot classify the object. To avoid object selection bias, we shufle the objects randomly.
Now we move to describe the datasets used in this setting, then talk about the results of the experiments.
The training examples revolve around messages that are classified as real threats by human analysts. These messages were collected using a system which is a part of a commercial product1. The only constraint on these examples is being published on the underground forums in 2021 and on. These examples constitute the positive training dataset part. We checked the underground forums where these messages were written, and the list of these forums is used to generate the negative examples, in a way such that for each positive example of a forum, =* negative examples are collected randomly w.r.t the date constraint, where is a factor, called balance ratio, which will be controlled in the experiments. The number of positive training examples is 595. The testing was performed on 960 positive examples and the negative testing examples were constructed in the same manner as training negative examples. These messages are collected from 12 diferent forums. Several experiments will be run with changing several parameters that might afect the final results. These factors are: 1. Dataset size and distribution: the only constant we have is the number of positive examples used. We test several sizes of negative/positive balance ratio values. In addition to 1Provided by the cybersecurity firm Group-IB.
this, we try to make a less random choice of negative examples, by filtering messages that might be spam messages (for instance, messages like “thanks” or “up” are considered to be of low value). We can also choose messages posted only in subsections of forums that are relevant to the classification (if we are trying to find messages about database leaks, we do not need messages coming from the credit cards section). Filtering based on message length is needed also, because some messages are articles, and while they would contain a lot of triggering keywords, they are not actual threats. 2. The intersection operator: we used set-theoretic intersection, then we use interval intersection (We will look into two-sided and one-sided intervals). 3. The number of attributes: the attributes are the values of tf-idf for the words of the messages, and changing the number of words to be in the attributes list is examined, and for which popularity of the keyword we can ignore it and remove it from the list is also considered. The values of attributes in case of theoretic set intersection are binary (the message either have the keyword or not). In case of interval intersection, the value of the attribute would be an interval beginning and ending with the tf-idf value. 4. The tolerance factor , which represents the probabilistic relaxation allowed for counter examples.
We will have the usual classification assessment methods, but we need to be attentive to the case of unclassified examples. Handling unclassified examples can be done in three diferent ways: • Ignoring them by considering them negative examples, and that depends on how harsh our model is about classifying new examples. i.e., if the model classifies almost all positive examples as positive (high recall) and leaves only a very small number of unclassified examples relative to the number of new examples, then it might be possible to classify unclassified examples as negative, as the probability of them being actually positive is very low. This approach is not acceptable in cases where the cost of missing a positive example is high, which is the case for us, as missing a real threat is of a high cost. • Moving all the unclassified examples to a human analyst, so they can assess their credibility, which can be done only in case the number of unclassified examples is low. • Removing unclassified examples all together, by having a probabilistic relaxation of the classifier, so that it classifies examples based on how close they are to a class, not as zero-one state. examples ⊆ .
In addition to the usual definitions of assessment, we define another measure of the improvement this brings to human workers, by how much the messages they have to check shrunk in size. We call it "saved efort " and define as 1 − |||| , where is the set of unclassified
We first state our parameters that would be used in the future. We have |+| = positive examples and |− | = negative examples for the training dataset. We have zero unclassified examples in the training data. The number of negative examples = * where is a positive integer.
The number of attributes is labeled as . In the test dataset, we have positive examples and examples. The model might have a number of unclassified examples of the test dataset. This set of examples is labeled and it is divided in two subsets: true positive examples that were left unclassified by the model (labeled -) and true negative examples that were left unclassified by the model (labeled -).
In the method we described above, the explanation of the model is the intersection of attributes of the test object and the concept object that gave us the result of the classification (meaning that the extension of this intersection of attributes all have/do not have the attribute value). This set is denoted by .
While we can control the balance of the training dataset in our case, this might not be the real world situation, which means that we would have a varying range of the values of saved efort and F1 measure, presenting us with a trade-of between coverage and model predictions correctness.
We performed multiple experiments. The first one would have only binary attributes. The next would have intervals as attributes. In the next two experiments, the data is represented by onesided intervals. After this, we repeat the pattern structures experiments but with varying values for . Due to space limitations we present the results at https://github.com/abdulrahimGhazal/FCAresults
The attribute values here are TT-IDF values for the keywords contained in the vectorizer’s vocabulary resulting from building the tf-idf model. The value of the attribute in an object would be represented here as: _() = ︂{ 1 ∈ 0 ℎ (5) (6)
We test a range of 5 values of the ratio between the positive to negative examples in the training dataset (from 1 to 5). We also test 5 diferent values of _ which is a factor that controls the number of attributes that we would have. It specifies the threshold at which the TT-IDF builder ignores the term if it has less frequency in the documents. Theoretic set intersection is used.
The highest F1 in these experiments occurred on the first experiments where the dataset had the most keywords (lowest _ step) and the same goes for the saved efort measure. The highest value was F1 = 98.8 and saved efort = 88.8 at (ratio, _ ) = (1, 0.01).
We can observe peaks that happen when we reset the _ step in the training dataset, then a decline in the F1 afterwards until the next peak. This is a natural observation, since the _ step increases between the peaks, meaning that we increase the number of ignored keywords that might play a role in classifying the messages correctly.
We now repeat the same experiment, using only the lowest balance ratio, varying the values of _ , and also varying values of to allow for a certain small amount of counterexamples (objects of the other class matching the intersections used as classifiers).
The highest value was F1 = 98.6 at ( , ratio, _ ) = (90, 1, 0.01) and saved efort = 92.5 at ( , ratio, _ ) = (75, 1, 0.01).
Now we look at using pattern structures to classify underground messages by representing textual data as intervals (two-sided and one-sided).
In this next part, we represent the values of the tf-idf as intervals of the floating point value such as if the tf-idf value is , the attribute value would be [,]. In this setting, the intersection operator is defined as an interval that starts with the minimum of the two intervals’ starts and ends with the maximum of the two intervals’ ends.
[1, 1] ⊓ [2, 2] = [(1, 2), [1, 2)] (7)
The highest F1 in these experiments occurred on the first experiments where the dataset had the most keywords (lowest _ step) and the same goes for the saved efort measure. The highest value was F1 = 88.0 and saved efort = 87.7 at (ratio, _ ) = (1, 0.01). The values of F1 and saved efort decreases after that with increasing values of _ .
Here, we represent the values of the tf-idf as intervals of the floating point value such as if the tf-idf value is , the attribute value would be [,∞].
In this setting, the intersection operator is defined as an interval that starts with the maximum of the two intervals’ starts and ends with infinity.
[1, ∞] ⊓ [2, ∞] = [(1, 2), ∞] (8)
The highest F1 in these experiments occurred on the first experiments where the dataset had the most keywords (lowest _ step) and the same goes for the saved efort measure. The highest value was F1 = 88.0 and saved efort = 87.7 at (ratio, _ ) = (1, 0.01). The values of F1 and saved efort decreases after that with increasing values of _ . Here, we represent the values of the tf-idf as intervals of the floating point value such as if the tf-idf value is , the attribute value would be [,∞].
In this setting, the intersection operator is defined as an interval that starts with the minimum of the two intervals’ starts and ends with infinity.
The highest F1 in these experiments occurred on the first experiments where the dataset had the most keywords (lowest _ step) and the same goes for the saved efort measure. The highest value was F1 = 89.7 and saved efort = 87.6 at (ratio, _ ) = (1, 0.01). The values of F1 and saved efort decreases after that with increasing values of _ .
In this next part, we represent the values of the tf-idf as intervals of the floating point value such as if the tf-idf value is , the attribute value would be [,]. As in before, the intersection operator is defined as an interval that starts with the minimum of the two intervals’ starts and ends with the maximum of the two intervals’ ends.
The diference now is testing several values (see Algorithm 1).
[1, 1] ⊓ [2, 2] = [(1, 2), [1, 2)]
The highest value was F1 = 94.2 at ( , ratio, _ ) = (80, 1, 0.01) and saved efort = 94.1 at ( , ratio, _ ) = (75, 1, 0.01). The pattern noticed here is the F1 peaks we get when values of _ increases locally at constant values of , Then when we increase _ significantly, the values of F1 decreases again.
Here, we represent the values of the tf-idf as intervals of the floating point value such as if the tf-idf value is , the attribute value would be [,∞]. The diference now is testing several values (see Algorithm 1).
In this setting, the intersection operator is defined as follows:
[1, ∞] ⊓ [2, ∞] = [(1, 2), ∞]
The highest value was F1 = 91.7 at ( , ratio, _ ) = (95, 1, 0.01) and saved efort = 94.5 at ( , ratio, _ ) = ((85,90,95), 1, 0.01). The pattern noticed here is the F1 peaks we get when values of _ increases locally at constant values of , Then when we increase _ significantly, the values of F1 decreases again.
(9) (10) (11)
Here, we represent the values of the tf-idf as intervals of the floating point value such as if the tf-idf value is , the attribute value would be [,∞]. The diference now is testing several values (see Algorithm 1).
In this setting, the intersection operator is defined as an interval that starts with the minimum of the two intervals’ starts and ends with infinity.
The highest value was F1 = 94.1 at ( , ratio, _ ) = (75, 1, 0.01) and saved efort = 94.2 at ( , ratio, _ ) = ((75,80), 1, 0.01). The pattern noticed here is the F1 peaks we get when values of _ increases locally at constant values of , Then when we increase _ significantly, the values of F1 decreases again.
Looking at the results, we can see that the binary values of the attributes model performed the best, because the attributes values and intersection method there (the theoretical set intersection) is the most restrictive among all others, giving a little room for error, but the issue with such method is that it sufers from this restrictions when totally new keywords are introduced, as it does not accept any keywords which were not used in the exact intersection.
We can also see that the less restrictive the conditions of the intersection, the less accurate it will be. The best conditions of pattern structures in non-binary representation of the data in our example is the Minimum one-sided intervals, because by its nature, it is the most inclusive of values that are non-zero in the classification scheme.
The next best one is the Maximum one-sided interval. While worse than the Minimum onesided interval, because it is restricting attribute values to a smaller interval, it still outperforms the interval representation, because of how limited the values of interval representation are.
When relaxation is introduced, we can see that the values of F1 and the saved efort are higher than in the case with no relaxation, supporting that flexibility is useful in case of text messages classification.
The sizes of the - were always smaller than -, because of the limited set of keywords the model would have compared to the large amount of possible negative messages’ keywords.
Underground forum messages are hackers announcements that are shared on the internet about attacks or tools used to carry out attacks. We presented an FCA-based approach for classifying forum messages based on their probability of being risky. The results of experiments show that the use of binary attributes (standard FCA) gave better accuracy, while the use of interval pattern structures gave better saved efort.
The article was prepared within the framework of the Basic Research Program at HSE University, RF [17] S. O. Kuznetsov, Fitting pattern structures to knowledge discovery in big data, in: International conference on formal concept analysis, Springer, 2013, pp. 254–266.