# Empirical Analysis of Capacity Investment Solution in Distribution Grids

Luis Lopez, Alvaro Gonzalez-Castellanos, David Pozo  Center for Energy Science
and Technology
Skolkovo Institute of Science and Technology (Skoltech)
Moscow, Russia
{luis.lopez, alvaro.gonzalez<EMAIL_ADDRESS>
###### Abstract

This paper presents an analysis of the stability and quality of the
distributed generation planning problem’s investment solution. The entry of
distributed generators power based on non-conventional energy sources has been
extensively promoted in distribution grids. In this paper, a two-stage
stochastic programming model is used to find the optimal distributed
generators’ installed capacities. We emphasize the design of scenarios to
represent the stochasticity of power production on renewable sources. In the
scenario generation, a method is proposed based on the clustering of real
measurements of meteorological variables. We measure the quality and stability
of the investment solution as a function of the number of scenarios. The
results show that a reduced selection of scenarios can give an inadequate
solution to distributed generators’ investment strategy.

###### Index Terms:

Clustering, Distributed generators, Investment solution, Stochasticity.

##  I Introduction

In modern distribution networks, users can inject active power into the grid
by small power plants [1]. The power plants connected near the demand buses
are called distributed generation units (DG units) [2]. Large amounts of power
are being injected through DG units due to policies that promote non-
conventional renewable energies in different countries [3, 4, 5]. With DG’s
widespread deployment, the distribution system operator needs to plan and
coordinate the new DG units’ installation capacity. DG planning can reduce
operating costs or solve technical restrictions [6].

The investment solution in distribution networks refers to determine the
installed capacities and locations of DG units. When DG units are power-based
on non-conventional renewable technologies, they behave as non-controllable
and stochastic negative load. Thus, we need to capture the uncertainty
associated with meteorological measurements [7]. Modeling the stochasticity of
renewable generation sources has been widely confronted by several authors [8,
9, 2, 6]. Jooshaki et al. [10] propose a tool to integrate DG units using a
mixed-integer linear stochastic model and perform a case study on a 24-node
distribution network. In [11], the authors proposed a methodology using mixed-
integer stochastic programming to find the best reinforcement plan for
mitigating greenhouse gas emissions. In [12], a stochastic model is proposed
to address the problem of distribution system expansion with uncertainties of
DG units and issues related to CO2 emissions [13].

Stochastic programming is a mathematical framework that lets capturing the
uncertainty of power production from non-conventional renewable sources [14,
15]. It has been proposed in [16] to use Sample Average Approximation (SAA) to
generate scenarios in the planning problem with stochastic parameters.
Nevertheless, scenario generation techniques are limited because they are an
approximation (discrete scenarios) of real distribution. Therefore, the
stochastic model relies on scenario representation, and if scenario
representation is deficient, information about the actual probability
distribution may be lost. This work proposes a two-stage stochastic
programming model that provides an investment solution considering short-term
uncertainty in a long-term planning problem. We propose the k-means clustering
technique for the scenario generation to reduce the problem’s dimensionality
and capture the underlying correlation between the random variables. We
analyze the quality of the investment solution as a function of the number of
scenarios used. We calculate the expected value and the dispersion of the
solution obtained and upper and lower bound of the investment solution for
each number of scenarios.

The main contribution of this work is the analysis of the quality and
stability of the investment solution in the DG planning problem using
empirical measurements. We assess how the investment solution deviates from
its ground-truth value when we use an inadequate description of the problem’s
stochasticity (few numbers of scenarios). The work is organized as follows:
Section II describes the two-stochastic programming model and the estimation
of the upper and lower boundaries. Section III introduces the case study and
the scenario generation technique. Section IV shows the findings and
simulations performed on a test distribution system with real measurements.
Section V provides the discussions and conclusions of the observed empirical
stability.

##  II Methodology

Stochastic programming provides solutions using scenarios to represent
possible realizations of the uncertainty. This section describes our
methodology for solving the problem of investment in DG units using stochastic
programming. In Section II-A, we briefly describe the model used and in
Section II-B, we describe the metrics to evaluate the quality of the solution
obtained.

###  II-A Two-stage problem formulation

This article addresses the problem of DG planning through a two-stage
stochastic programming approach (Fig. 1). The first stage consists of the
investment solution of the DG units. Three technologies of DG units are
considered: solar photovoltaic (PV), wind turbines (WT), and conventional
generators (CG). The first-stage variables are integers since the power plant
units are manufactured in discrete modules of installed power. The second
stage consists of the computation of the operation and maintenance cost for
every scenario. The second stage calculates the expected value of the power
produced by the newly installed DG units. The uncertainty of power production
and energy balance is associated with the meteorological variables of solar
radiation, wind speed, temperature, and energy demand. The evaluation of the
expected value of power production given an investment decision requires
numerous second-stage optimization problems that depend on the number of
scenarios. In summary, this stochastic DG planning problem involves a large
number of scenarios and integer variables in the first stage.

Model 1 Sitting and sizing of distributed generation with non-conventional
renewable energies

Objective:

$\displaystyle\text{min}\;(\pi^{\text{inv}}+\pi^{\text{OM}})$ (1)

Constraints:

$\displaystyle\pi^{\text{inv}}=\smashoperator[]{\sum_{n,\text{tech}}^{}}\left(\pi^{\text{inv},\text{tech}}x^{\text{tech}}_{n}\right)$
(2)
$\displaystyle\pi^{\text{OM}}=\smashoperator[]{\sum_{\tau}^{}}N_{\tau}\rho_{\tau}\pi^{\text{OM}}_{\tau}$
(3)
$\displaystyle\pi^{\text{OM}}_{\tau}=\pi^{\text{loss}}_{\tau}+\pi^{\text{SS}}_{\tau}+\pi^{\text{DG}}_{\tau}$
(4)
$\displaystyle\pi^{\text{loss}}_{\tau}=\pi^{\text{loss}}\smashoperator[]{\sum_{n,m\in
L}^{}}S_{b}R_{n,m}i^{2}_{n,m,\tau}$ (5)
$\displaystyle\pi^{\text{SS}}_{\tau}=\pi^{\text{SS}}_{\tau}S_{b}p^{\text{SS}}_{\tau}$
(6)
$\displaystyle\pi^{\text{DG}}_{\tau}={S_{b}}\smashoperator[]{\sum_{n,\text{tech}}^{}}\pi^{\text{OM},\text{tech}}p^{\text{tech}}_{n,\tau}$
(7)
$\displaystyle\gamma_{\tau}^{\text{D}}P^{\text{D}}_{m}{=}\smashoperator[]{\sum_{n,m\in
L}^{}}\left(p^{n,m}_{\tau}{-}p^{m,n}_{\tau}\right){-}R_{n,m}i^{2}_{n,m,\tau}{+}\sum_{\text{tech}}p^{\text{tech}}_{m,\tau}{+}p^{\text{SS}}_{m,\tau}$
(8)
$\displaystyle\gamma_{\tau}^{\text{D}}Q^{\text{D}}_{m}{=}\smashoperator[]{\sum_{n,m\in
L}^{}}\left(q^{n,m}_{\tau}{-}q^{m,n}_{\tau}\right){-}X_{n,m}i^{2}_{n,m,\tau}{+}\sum_{\text{tech}}q^{\text{tech}}_{m,\tau}{+}q^{\text{SS}}_{m,\tau}$
(9)
$\displaystyle{{2}\left(R_{n,m}p^{n,m}_{\tau}{+}X_{n,m}q^{n,m}_{\tau}\right)}{=}v^{2}_{n,\tau}{+}{\left|Z_{n,m}\right|^{2}i^{2}_{n,m,\tau}}{+}v^{2}_{m,\tau}\hskip
12.0pt$ (10) $\displaystyle
w_{n,m,\tau}\geq\underline{V}i^{2}_{n,m,\tau}+v^{2}_{n,\tau}\underline{I}^{2}_{n,m}-\underline{I}^{2}_{n,m}\underline{V}$
(11) $\displaystyle
w_{n,m,\tau}\geq\overline{V}i^{2}_{n,m,\tau}+v^{2}_{n,\tau}\overline{I}^{2}_{n,m}-\overline{I}^{2}_{n,m}\overline{V}$
(12) $\displaystyle
w_{n,m,\tau}\leq\overline{V}i^{2}_{n,m,\tau}+v^{2}_{n,\tau}\underline{I}^{2}_{n,m}-\overline{V}\underline{I}^{2}_{n,m}$
(13) $\displaystyle w_{n,m,\tau}\leq
v^{2}_{n,\tau}\overline{I}^{2}_{n,m}+\underline{V}i^{2}_{n,m,\tau}-\underline{I}^{2}_{n,m}\overline{I}^{2}_{n,m}$
(14) $\displaystyle\underline{V}^{2}\leq v^{2}_{n,\tau}\leq\overline{V}^{2}$
(15) $\displaystyle i^{2}_{n,m,\tau}\leq\overline{I}^{2}_{n,m}$ (16)
$\displaystyle\overline{P}^{\text{PV}}x^{\text{PV}}_{n}+\overline{P}^{\text{WT}}x^{\text{WT}}_{n}+\overline{P}^{\text{CG}}x^{\text{CG}}_{n}\leq\overline{P}_{n}$
(17) $\displaystyle 0\leq
p^{\text{tech}}_{n,\tau}\leq\gamma^{\text{tech}}_{\tau}\overline{P}^{\text{tech}}x^{\text{tech}}_{n}\beta^{\text{tech}}_{n}$
(18) $\displaystyle\lambda^{\text{tech},+}p^{\text{tech}}_{n,\tau}\leq
q^{\text{tech}}_{n,\tau}\leq\lambda^{\text{tech},-}p^{\text{tech}}_{n,\tau}$
(19)
$\displaystyle\lambda^{\text{tech},\text{+/-}}=\mp\tan(\cos^{-1}(\text{pf}^{\text{+/-}}))$
(20) $\displaystyle\pi^{\text{inv}}\leq\Pi^{\text{bgt}}\vspace{-4\jot}$ (21)

Figure 1: Two-stage stochastic approach.

The objective function (1) minimizes the system’s energy cost over the
analyzed time horizon. The energy cost is the sum of the investment cost and
the total cost of operation and maintenance. The investment cost (2) is equal
to the sum of the installation costs per technology in each node. The total
cost of operation and maintenance (3) is the sum of the probability of
occurrence multiplied by operation and maintenance costs in each of the
scenarios generated. Each scenario’s operation and maintenance costs depend on
the costs of active power losses, the energy imported from the power grid, and
the new DG units’ power production costs. Demand profiles and weather
conditions only depend on the scenario and not on the system nodes since
distribution networks cover the same area.

The constraints of the stochastic DG planning approach are divided into
physical law constraints (8)-(10) and engineering constraints (15)-(20). The
physical law constraints are the active and reactive power balance constraints
(generated power must supply the demand power) and the power flow constraints
through the transmission lines. The power flow constraints are modeled through
the DistFlow equations [17, 18]. The McCormick envelope (11)-(14) is used as a
relaxation technique to solve the product of two bounded variables in
calculating the apparent power of the DistFlow equations. Engineering
constraints are set by the distribution system operator and include node
voltage limits, line loadability limits, installed DG capacity limits,
reactive power DG limits set by power factors, and investment limits
determined by the available budget (21).

###  II-B Quality and stability of the solution

Our investment problem formulation described in Model 1 can be compactly
summarizes as a classical two-stage stochastic optimization problem (22).

$\displaystyle z^{*}=\text{min}$ $\displaystyle
c^{T}x+\mathbb{E}_{P}\left[d^{T}\mathbf{y}\right]$ (22a) s.t.: $\displaystyle
x\in X$ (22b) $\displaystyle\mathbf{y}\in\mathbf{Y}(x)$ (22c)

The vector $x$ is representing investment decisions at the first stage while
the random vector $\mathbf{y}$ represents the operational decisions at the
second stage. The objective (22a) aims to minimize the capital and expected
operational costs. At the same time, the budget-limit constrains and power
grid operational feasibility constraints are represented by (22b) and (22c),
respectively. The symbol $\mathbb{E}_{P}$ is the expected operator over the
random parameter distribution $P$. If $P$ represents a continuous distribution
vector, this problem is infinite-dimensional, and different approaches have
been proposed for solving it.

In rest of this subsection, we describe the metrics to evaluate the investment
solution’s quality and stability. We will use the sample-average approximation
(SAA) method, [16] for approximating the problem (22).

A particular feature of this work is that data is collected from a real grid.
Thus, instead of inferring continuous parametric distributions, we use
directly observed data in the investment problem addressed here. Still, data
can potentially be massive, so we need to find means to reduce the problem’s
computational complexity. We denote by $N$ to the total number of collected
data points, i.e., scenarios.

In this work, the scenarios are generated using the k-means clustering
technique explained in Section III-A. To discuss the optimal value limits, we
assume the following: (i) the solution has a mean and finite variance. (ii)
scenario sampling can be generated in different numbers. (iii) the objective
function can be evaluated for the stochastic parameters of the generated
outputs.

####  II-B1 Lower bound estimation

Using the SAA algorithm, we estimate the value of the lower bound of the DG
planning problem’s investment solution. To evaluate the lower bound, we solve
$m$ replicas of the two-stage problem (22) with $n$ scenarios (where $n<N$).
We initially generate $m$ sample candidates independently with $n$ scenarios
and then solve the approximated sample-based optimization problem (23).
Optimal objective of this problem is a lower bound of the original problem
(22), i.e., $\mathbf{LB}_{m}(n)\leq z^{*}$ for any replica $m$. Because the
$n$-drawn scenarios are random, the LB is also random parameter.

$\displaystyle\textbf{LB}_{m}(n)=\text{min }$ $\displaystyle
c^{T}x+\frac{1}{n}\sum_{k=1}^{n}d^{T}y_{k}$ (23a) s.t.: $\displaystyle x\in X$
(23b) $\displaystyle y_{k}\in Y_{k}(x)$ (23c)

####  II-B2 Upper bound estimation

Given a trial (not necessarily optimal) solution for the first stage decision
variables denoted by $\hat{x}$, we can compute an upper bound of the original
problem (22) by (24), i.e., $z^{*}\leq\text{UB}_{m}(\hat{x})$.

$\displaystyle\text{UB}_{m}(\hat{x})=c^{T}\hat{x}+\mathbb{E}_{P}\Big{[}\min_{\mathbf{y}\in\mathbf{Y}(\hat{x})}$
$\displaystyle d^{T}\mathbf{y}\Big{]}$ (24)

Optimization problem (24) is scenario-decomposable due to the fixed value of
the first-stage decision variables. When the probability distribution function
$P$ is discrete, the expected value can be computed exactly compute for each
possible random states that can be observed (scenarios). However, if the
number of discrete values of the probability distribution $P$ is large or $P$
is continuous, we can approach the upper bound by the (25) – Law of large
numbers.

$\displaystyle\textbf{UB}_{m}(\hat{x},\widehat{N})=c^{T}\hat{x}+\frac{1}{\widehat{N}}\sum_{k=1}^{\widehat{N}}+\;\text{min
}$ $\displaystyle d^{T}y_{k}$ (25a) s.t.: $\displaystyle y_{k}\in
Y_{k}(\hat{x})\quad$ (25b)

The firs observation is that $\textbf{UB}_{m}(\hat{x},\widehat{N})$ is random
when $\hat{N}$ random scenarios are drawn. The second observation is that for
discrete distributions, as in this paper, the random
$\textbf{UB}_{m}(\hat{x},\widehat{N})$ should be approaching to the
deterministic $\text{UB}_{m}(\hat{x})$ when $\widehat{N}\to N$.

Finally, we can estimate the optimal solution gap between the lower and upper
bounds (26), that gives statistical information about the stability of the
problem.

$\displaystyle\textbf{gap}_{m}(\hat{x},n,\widehat{N})$ $\displaystyle=$
$\displaystyle\textbf{UB}_{m}(\hat{x},\widehat{N})-\textbf{LB}_{m}(n)$ (26)

##  III Scenario generation and test case

There are several methods for generating scenarios from a known probability
distribution or a large historical data set. In this section we present the
scenario generation technique based on clustering (Section III-A). In
addition, we present a description of the case study for the computational
tests in Section III-B.

###  III-A Scenario generation

In the stochastic programming model, we analyze four parameters of
uncertainty: solar radiation (W/m2), wind speed (m/s), temperature (°C), and
active power consumption (W). We use a set of historical data measured with a
weather station for weather data and a power meter for active power data. The
database has hourly measurements of the uncertainty parameters over one year
of recording. The technique used for the generation of scenarios is the
k-means clustering technique [19]. The k-means technique is a method to create
representative clusters of a data group, whose partitions are given in $k$
clusters. All $k$ clusters have a centroid representing the mean value of the
uncertainty parameters contained in that set, minimizing variances within each
cluster.

The generation of scenarios is done using the historical record of uncertainty
parameters (Fig. 2). Initially, we generate a $k$ number of clusters
containing representative data of solar radiation, wind speed, temperature,
and power demand. Then we calculate the probability of occurrence of that
scenario depending on the cluster’s size (amount of data it represents) over
the total of registered empirical scenarios. Then, the weather variables are
the input to the power production models (27)-(29) of the DG units. The power
production model of the PV units depends on solar radiation and ambient
temperature, as worked in [20, 21]. The power production model of WT depends
only on wind speed. All variables are standardized to fit later on the
distribution system.

$\displaystyle P^{\text{PV}}$ $\displaystyle=$ $\displaystyle
Y^{\text{PV}}\left(\frac{G_{T}}{{G}_{T}^{\text{STC}}}\right)\left[1-\alpha\left(T_{c}-T_{c}^{\text{STC}}\right)\right]$
(27) $\displaystyle T_{c}$ $\displaystyle=$ $\displaystyle
T_{a}+\frac{G_{T}}{G_{T}^{\text{NOCT}}}\left(T_{c}^{\text{NOCT}}-T_{a}^{\text{NOCT}}\right)$
(28) $\displaystyle P^{\text{WT}}$ $\displaystyle=$
$\displaystyle\begin{cases}Y^{\text{WT}}\frac{v-v_{i}}{v_{r}-v_{i}},&v_{i}\leq
v<v_{r}\\\ Y^{\text{WT}},&v_{r}\leq v<v_{o}\\\ 0,&\text{otherwise}\end{cases}$
(29)

Figure 2: Scenario generation methodology.

###  III-B Case study

The stability analysis of the investment solution is applied to the 34-node
distribution system with the topology presented in [22]. The total installed
demand of the system is 5.4 MW with an average power factor of 0.85 in the
lag. Historical data was recorded from January 1 to December 31, 2018 with a
weather station with an elevation of 36m and 11.02°N - 74.85°W. The two-stage
stochastic programming problem was formulated using JuMP v0.21.3 and Gurobi
v9.0.1 which provides a solver for the stochastic programming framework. The
test machine features OS Name Microsoft Windows Server 2016 Standard, Intel(R)
Xeon(R) Gold 6148 CPU @ 2.40GHz, 2394 Mhz, 20 Core(s), 40 Logical
Processor(s), Total Physical Memory 256 GB.

Figure 3: Empirical distribution clustering ($n=10$).

##  IV Results and simulations

For the DG planning problem, we apply stability tests for the investment
solution with different numbers of generated scenarios. For scenario size $n$,
we solve the optimization problem a total of 10 times (replications). The
reference value for the solution that we call ground truth is calculated with
the maximum number of scenarios that we computationally manage to solve
($n^{\prime}=5000$).

Figure 4: Optimal objective function, estimated lower bound, estimated upper
bound.

Fig. 4 shows the optimal solution’s value solution from (1), the estimated
lower boundary, and the estimated upper bound. We can see that the lower bound
varies with the number of scenarios generated. The optimal solution’s value
improves, and the optimality gap size narrows when we increase the generated
scenarios’ size. This mainly results from the fact that the lower bounds
variance decreases as we approach the full empirical distribution. This occurs
because the generated scenarios are clustered, and their values may be outside
the initial set. The previous problem can be solved with much higher
replication values, but it would considerably increase the simulation time
(Fig. 5).

Figure 5: Solution time for the optimization problem.

The results show that using a few scenarios to solve a stochastic programming
problem can lead to substantial errors and sub-optimal solutions.
Additionally, the actual probability distribution and stochasticity may not be
properly represented in the generated scenarios.

Fig. 6 shows the in-sample stability calculated as the optimal solution’s
relative value in the $n$ scenario vs. the optimal ground actual value. Also,
Fig. 6 shows that in-sample stability is improved when we increase the number
of scenarios used significantly. On the other hand, Fig. 7 shows the out-of-
sample stability for different numbers of scenarios. The in-sample stability
is calculated using the equations and based on our previous notation; the
optimal derived values are calculated using the different scenarios (M sets of
scenarios with N scenarios each). On the other hand, to calculate out-of-
sample stability, we will insert the fixed first-stage solution of each sample
m with n size into an optimization problem using the N-scenarios, representing
the true distribution. From the figures, we can conclude that high variability
in in-sample stability is correlated with high out-of-sample variability.

Figure 6: In-sample Stability. Figure 7: Out-sample Stability.

Additionally, we plot the distribution of technologies in a normalized fashion
under different numbers of generated scenarios. Fig. 8 shows the mix of
installed capacities when there is no budget constraint. We can see that the
installed capacities highly fluctuate when we have a small number of
scenarios, while that variability becomes smaller when we have a more
significant number of scenarios. Analogously,

Figure 8: Normalized DG units’ installed capacities mix.

##  V Conclusions

This paper applies the SAA technique and stability tests to evaluate the
distributed network investment solution’s quality using empirical
measurements. We show that an investment solution based on a few scenarios can
lead to misestimates and deviations from the true solution. On the other hand,
the representation of stochasticity and scenarios’ use affects the quality of
the solution obtained when we have several parameters of uncertainty. From the
stability perspective, we can conclude that the solution satisfies the
criteria of in-sample and out-of-sample stability when the number of scenarios
generated surpasses 1000 data points for this particular distribution grid. In
perspective with the stability tests, we can conclude that the model has a
good out-of-sample stability performance (the deviations from the optimum
relative value are less than 10% for all scenarios). For the in-sample
stability test, we can conclude that for a number of scenarios greater than
500, the deviations from the optimal value are less than 10%. The SAA
algorithm evaluates the solution’s quality with the optimality gap using the
estimated lower and upper limits. We can conclude that the quality of the
solution depends on the number of scenarios used. The optimality gap is
reduced to the variability of less than 10% when the number of scenarios
generated is higher than 1000.The optimal of the shared technologies depends
on the number of scenarios used; few scenarios lead to a high energy mix
variation. A poor representation of the scenarios can lead to an oversize of
conventional technologies that derive excess operational costs for the
distribution network operator. Finally, we recommend using scenario generation
techniques to capture and represent the uncertainty parameters’ real
distributions adequately. Besides, using as large a number of scenarios as is
computationally feasible is highly recommended to find stable and quality
solutions to stochastic DG planning.

## References

  * [1] S. Kakran and S. Chanana, “Smart operations of smart grids integrated with distributed generation: A review,” _Renewable and Sustainable Energy Reviews_ , vol. 81, pp. 524–535, 1 2018.
  * [2] B. Singh and J. Sharma, “A review on distributed generation planning,” _Renewable and Sustainable Energy Reviews_ , vol. 76, pp. 529–544, 9 2017\.
  * [3] P. Pereira da Silva, G. Dantas, G. I. Pereira, L. Câmara, and N. J. De Castro, “Photovoltaic distributed generation – An international review on diffusion, support policies, and electricity sector regulatory adaptation,” _Renewable and Sustainable Energy Reviews_ , vol. 103, pp. 30–39, 4 2019.
  * [4] M. Q. Duong, N. T. Nam Tran, G. N. Sava, and M. Scripcariu, “The impacts of distributed generation penetration into the power system,” in _2017 International Conference on Electromechanical and Power Systems (SIELMEN)_. IEEE, 10 2017, pp. 295–301.
  * [5] J. Dong, T. Feng, H. Sun, H. Cai, R. Li, and Y. Yang, “Clean distributed generation in China: Policy options and international experience,” _Renewable and Sustainable Energy Reviews_ , vol. 57, pp. 753–764, 5 2016\.
  * [6] S. Jain, S. Kalambe, G. Agnihotri, and A. Mishra, “Distributed generation deployment: State-of-the-art of distribution system planning in sustainable era,” _Renewable and Sustainable Energy Reviews_ , vol. 77, pp. 363–385, 9 2017.
  * [7] G. Notton, M. Nivet, C. Voyant, C. Paoli, C. Darras, F. Motte, and A. Fouilloy, “Intermittent and stochastic character of renewable energy sources: Consequences, cost of intermittence and benefit of forecasting,” _Renewable and Sustainable Energy Reviews_ , vol. 87, pp. 96–105, 5 2018\.
  * [8] A. Zakaria, F. B. Ismail, M. H. Lipu, and M. Hannan, “Uncertainty models for stochastic optimization in renewable energy applications,” _Renewable Energy_ , vol. 145, pp. 1543–1571, 1 2020.
  * [9] A. Gonzalez-Castellanos, D. Pozo, and A. Bischi, “Stochastic Unit Commitment of a Distribution Network with Non-ideal Energy Storage,” in _2019 International Conference on Smart Energy Systems and Technologies (SEST)_. IEEE, 9 2019, pp. 1–6.
  * [10] M. Jooshaki, H. Farzin, A. Abbaspour, M. Fotuhi-Firuzabad, and M. Lehtonen, “A Model for Stochastic Planning of Distribution Network and Autonomous DG Units,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 6, pp. 3685–3696, 6 2020.
  * [11] J. M. Home-Ortiz, O. D. Melgar-Dominguez, M. Pourakbari-Kasmaei, and J. R. S. Mantovani, “A stochastic mixed-integer convex programming model for long-term distribution system expansion planning considering greenhouse gas emission mitigation,” _International Journal of Electrical Power and Energy Systems_ , vol. 108, pp. 86–95, 6 2019.
  * [12] T. D. De Lima, A. Tabares, N. B. Arias, and J. F. Franco, “A Stochastic Programming Model for the Planning of Distribution Systems Considering Renewable Distributed Generation and CO2 Emissions,” in _2019 IEEE PES Conference on Innovative Smart Grid Technologies, ISGT Latin America 2019_. Institute of Electrical and Electronics Engineers Inc., 9 2019.
  * [13] J. López, D. Pozo, J. Contreras, and J. R. Mantovani, “A convex chance-constrained model for reactive power planning,” _International Journal of Electrical Power and Energy Systems_ , vol. 71, pp. 403–411, 10 2015\.
  * [14] A. Narayan and K. Ponnambalam, “Risk-averse stochastic programming approach for microgrid planning under uncertainty,” _Renewable Energy_ , vol. 101, pp. 399–408, 2 2017.
  * [15] Z. Zhou, J. Zhang, P. Liu, Z. Li, M. C. Georgiadis, and E. N. Pistikopoulos, “A two-stage stochastic programming model for the optimal design of distributed energy systems,” _Applied Energy_ , vol. 103, pp. 135–144, 3 2013.
  * [16] P. Seljom and A. Tomasgard, “Sample average approximation and stability tests applied to energy system design,” _Energy Systems_ , 10 2019.
  * [17] M. E. Baran and F. F. Wu, “Optimal sizing of capacitors placed on a radial distribution system,” _IEEE Transactions on Power Delivery_ , vol. 4, no. 1, pp. 735–743, 1989.
  * [18] ——, “Optimal capacitor placement on radial distribution systems,” _IEEE Transactions on Power Delivery_ , vol. 4, no. 1, pp. 725–734, 1989\.
  * [19] A. K. Jain, “Data clustering: 50 years beyond K-means,” _Pattern Recognition Letters_ , vol. 31, no. 8, pp. 651–666, 6 2010.
  * [20] Y. Atwa, E. El-Saadany, M. Salama, and R. Seethapathy, “Optimal Renewable Resources Mix for Distribution System Energy Loss Minimization,” _IEEE Transactions on Power Systems_ , vol. 25, no. 1, pp. 360–370, 2 2010.
  * [21] Y. Riffonneau, S. Bacha, F. Barruel, and S. Ploix, “Optimal Power Flow Management for Grid Connected PV Systems With Batteries,” _IEEE Transactions on Sustainable Energy_ , vol. 2, no. 3, pp. 309–320, 7 2011.
  * [22] M. Chis, M. Salama, and S. Jayaram, “Capacitor placement in distribution systems using heuristic search strategies,” _IEE Proceedings - Generation, Transmission and Distribution_ , vol. 144, no. 3, p. 225, 1997.


# Mining actionable information from security forums: the case of malicious IP
addresses

Joobin Gharibshah1, Tai Ching Li1, Andre Castro1,
Konstantinos Pelechrinis2, Evangelos E. Papalexakis1 and Michalis Faloutsos1 2
School of Information Sciences, University of Pittsburgh, Pittsburgh, PA
Email<EMAIL_ADDRESS>1 University of California - Riverside, CA
Email<EMAIL_ADDRESS>
###### Abstract

The goal of this work is to systematically extract information from hacker
forums, whose information would be in general described as unstructured: the
text of a post is not necessarily following any writing rules. By contrast,
many security initiatives and commercial entities are harnessing the readily
public information, but they seem to focus on structured sources of
information. Here, we focus on the problem of identifying malicious IP
addresses, among the IP addresses which are reported in the forums. We develop
a method to automate the identification of malicious IP addresses with the
design goal of being independent of external sources. A key novelty is that we
use a matrix decomposition method to extract latent features of the behavioral
information of the users, which we combine with textual information from the
related posts. A key design feature of our technique is that it can be readily
applied to different language forums, since it does not require a
sophisticated Natural Language Processing approach. In particular, our
solution only needs a small number of keywords in the new language plus the
user’s behavior captured by specific features. We also develop a tool to
automate the data collection from security forums. Using our tool, we collect
approximately 600K posts from 3 different forums. Our method exhibits high
classification accuracy, while the precision of identifying malicious IP in
post is greater than 88% in all three forums. We argue that our method can
provide singificantly more information: we find up to 3 times more potentially
malicious IP address compared to the reference blacklist VirusTotal. As the
cyber-wars are becoming more intense, having early accesses to useful
information becomes more imperative to remove the hackers first-move
advantage, and our work is a solid step towards this direction.

Keywords: Security, Online communities mining, Forums

##  I Introduction

How can we take the first-mover advantage away from hackers? We argue that
hacker forums provide information earlier than other sources, and we should
leverage these forums in our security intelligence. Here, we focus on a
specific question. In particular, we want to extract as much useful
information from hacker/security forums as possible in order to perform
(possibly early) detection of malicious IP addresses, e.g., prior to their
appearance on blacklists. The latter can exhibit large delays in their update
and hence, new ways for labeling malicious IP addresses are needed [15]. In
this study we will use the term “hacker forums” to describe online forums with
a focus on security and system administration. Interestingly, we can classify
these forums into categories: (a) main stream forums, like Wilders Security,
and (b) “fringe” forums, like Offensive Community, where we find users with
names like satan911. Some of these forums have been known to have hackers
boast of attacks they have mounted, or sell tools for malicious purposes
(think rent-a-botnet). For example, in our dataset there is a post that
mentions “I give you a second server to have your fun with. Multiple websites
on this server. So let’s see if anyone can actually bring down the server”.
Right after that the hacker posted the IP, username and password for anyone to
access the server. In fact, there is a show-off section in these forums for
people to broadcast their hacking “skills”.

The overarching goal of this work is to mine the unstructured, user-generated
content in security forums. Specifically, we focus here on collecting
malicious IP addresses, which are often reported at such forums. We use the
term security forum to refer to discussion forum with a focus on security,
system administration, and or more generally, systems-related discussions. The
users in these forums include: security professionals, hobbyists, and hackers,
who go on these forums to identify issues, discuss solutions, and in general
exchange information.

Let us provide a few examples of how users report IP addresses, which may or
may not be malicious. Posts could talk about a benign IP address, say in
configuration files, as in the post:

"[T]his thing in my hosts file: 64.91.255.87 … [is] it correct?".

At the same time, posts could also report compromised or malicious IP
addresses, as in the post:

"My browser homepage has been hijacked to http://69.50.191.51/2484/".

The challenge is to automatically distinguish between the two. By doing so, we
can provide a new source of information of malicious IP addresses directly
from the affected individuals. Formally, we can state the problem as follows:

Key Question: Malicious IP Detection. Given a set of posts $\mathcal{P}_{F}$
that may contain IP addresses and users $\mathcal{U}_{F}$ of a security forum
$F$, as well as, the features $\Phi_{p},~{}\forall p\in\mathcal{P}_{F}$ and
$\Phi_{u},~{}\forall u\in\mathcal{U}_{F}$ for the posts and the users
respectively, can we determine if a given IP address $i$ is malicious or not?

The set of features $\mathcal{P}_{F}$ includes attributes such as the text of
the post, the posting user, the time of post, etc., while $\mathcal{U}_{F}$
includes information such as the date of a user joining the forum, the number
of posts the user has made etc. The above problem has two associated
questions:

a. Exclusivity: How many IP Addresses can we find that are never reported by
other reference sources?

b. Early warning: How much earlier are malicious IP Addresses reported in a
forum compared to reference sources, for the IP Addresses reported by both?

TABLE I: Extracting useful information; Number of malicious IP Addresses found by InferIP and not by VirusTotal.  | IP found by
---|---
Dataset | Total IP | Virus Total | InferIP only
Wilders Security | 4338 | 216 | 670
Offensive Community | 7850 | 339 | 617
Ashiyane | 8121 | 133 | 806

Most previous studies in this area have focused on structured information
sources, such as security reports, or malware databases. In fact, many efforts
focus on addressing security problems using knowledge obtained from the web,
as well as social and information networks. These efforts are mainly focused
on analyzing structured sources (e.g., [16]). However, studies assessing the
usefulness of (unstructured) information in online forums have only recently
emerged (e.g., [23]). These studies are rather exploratory and provide
evidence of the usefulness of the data in the forums, but do not provide a
systematic methodology or ready-to-use tools, which is the goal of our work.
We discuss existing literature in more detail later in section V.

The motivation of our work is to provide more information to security analysts
and systems. We want to enhance and complement, but not replace, existing
efforts for detecting malicious IP Addresses. For instance, many IP blacklists
enlist an IP as malicious after a number of reports above a pre-defined
threshold have been made for the specific address. Depending on the threshold
and the reactivity of the affected users/systems, this might take several
days, weeks or months. Therefore, a system, like the one proposed here, can
identify and point to malicious IP address to blacklist services and
firewalls.

We propose InferIP, a systematic approach for identifying malicious IP
Addresses among the IP addresses, which are mentioned in security forums. A
key novelty is that we use the behavioral information of the users, in
addition to the textual information from the related posts. Specifically, we
customize and use a Sparse Matrix Regression method on this expanded set of
features.

This paper presents an extension of our previous work [14]. Here, we add some
spatiotempral and behavioral analysis to extract the characteristics of the
identified IP addresses and the users who used these IP address in their
posts. Moreover, we investigate the ability of the proposed method to provide
early warning regarding malicious IP addresses.

By design, our framework is applicable to forums in different languages as it
relies only on the behavioral patterns of users and simple word counts, and
not a complex language-specific Natural Language Processing technique. From a
technical point of view the challenge in designing a solution to our Key
Question is most IP Addresses mentioned in these forums are not malicious. We
show that our system can add a significant number of previously unreported IP
address to existing blacklist services. Finally, as an engineering
contribution, we develop a customizable tool to facilitate the crawling of
forums, which we discuss in the next section.

Our results can be summarized into the following points:

a. Our method exhibits precision and recall greater than 88% and 85%
respectively, and an accuracy over malicious class above 86% in the 10-fold
cross validation tests we conducted for the three different forums. In
partially answering our Key Question, if our method labels a currently non-
blacklisted IP as malicious, there is a high chance that it is malicious,
given our high precision.

b. Our method identifies three times more malicious IP Addresses compared to
VirusTotal [5] a widely used aggregator of 60 blacklists of IP addresses.
Across our three forums, we find more than 2000 potential malicious IP
Addresses that were never reported by VirusTotal.

c. Our method identifies more than half of the IP addresses at least 3 month
earlier than VirusTotal. We study the malicious IP addresses that are
identified by both VirusTotal and InferIP. We find 53%, 71% and 62% of these
IP addreses in Wilders Security, Offensive Community and Ashiyane respectively
at least 3 months earlier than they were reported in VirusTotal.

d. The number of reported malicious IP addresses has increased by a factor 8
in 4 years. We find that the number of malicious IP addresses has increased
from roughly 100 in 2011 and 2012 to more than 800 in 2016. This could be
attributed to either an increase in the user base, an increase in the number
of attacks, or a combination of the two.

##  II Data Collection and Basic Properties

We have collected data from three different forums relevant to our study; (i)
Wilders Security [6], (ii) Offensive Community [4], (iii) Ashiyane [1]. The
first two forums are mainly written in English, while the last forum is an
Iranian forum, in Farsi111Our software and datasets will be made available at:
https://github.com/hackerchater/ .

Our data collection tool. We develop a customizable universal tool to make the
crawling forums easier. The challenge here is that each forum has its own
format and layout. Our tool requires only a custom configuration file, before
crawling a new forum. In configuration file, we specify entities in the forum
which are needed such as user ID, post’s date, post’s content and etc by XML
Path Language known as Xpath. Leveraging our current configuration files, the
task of crawling a new forum is simplified significantly. Using our crawler,
we collect data from three forums, two English and one in Farsi for a total
number of more than 30K users and 600K posts.

We use VirusTotal [5] as our reference blacklist IP addresses, since it is an
aggregator, and combines the information from over 70 other blacklists and
resources. VirusTotal is free to end users for non-commercial use and is a
private API to query the services in the rate of more than 4000 IP addresses
per minutes. It is provided upon requests for academic purposes.

We provide some basic statistics for our three forums in Table II. Offensive
Community and Ashiyane are two fringe forums in different languages. In these
forums there is a section where people openly boast about their achievement in
hacking. They share their ideas and tutorials on how to break into vulnerable
networks. On the other hand, Wilders Security as a mainstream forum is mostly
used to protect non-experts against attacks such as browser hijacking, and
provide solutions for their security problems.

For completeness, we present some of the terms we use here. A user is defined
by a login name registered with the site. The term post refers to a single
unit of content generated by a user. A thread refers to a collection of posts
that are replies to a given initiating post.

In Figures 1 and 2, we present the cumulative complementary distribution
function of the number of posts per user and the number of threads per users
respectively. As we can see in all the cases the distributions are skewed,
that is, most of the users contribute few posts in the forums and engage with
few threads. In Wilders Security, 85% of users post less than 10 posts each,
while 5.2% of the users post more than 50 posts. We find that 70% of the users
post in only one thread and only 8% of the users are active in more than 10
threads. This skewed behavior is typical for online users and communities
[12]. We will use features to capture aspects of both these user properties,
as we will see in the next section.

In Figure 3, we present the cumulative complementary distribution function of
the number of IP addresses that appear in each post. The skewed distribution
shows that most of the posts contain a few number of IP address. We find that
84.2% of the posts with IP addresses in Wilders Security and 84.1% in
Offensive Community have two or less IP addresses. In Ashiyane, 87.2% of these
posts contain less than two IP addresses. Interestingly, in Ashiyane, we find
1% of the IP containing posts with more than 100 IP addresses. We investigated
and we found that typically, these posts provide benign IP addresses of
proxies servers to fellow administrators.

TABLE II: The collected forums. Forum | Threads | Posts | Users | Active days
---|---|---|---|---
Wilders Security | 28661 | 302710 | 14836 | 5227
Offensive Comm. | 3542 | 25538 | 5549 | 1508
Ashiyane | 67004 | 279309 | 22698 | 4978

Groundtruth for training and testing. In order to build and evaluate, our
model we need to obtain a reasonably labeled dataset from IP addresses that
appear in the posts of the security forums. For that, we use the VirusTotal
service and assign malicious labels to an IP that has been reported by this
service. The number of malicious IP Addresses that we have used with the
corresponding posts are shown in table I as the IP found by VirusTotal. Note
that the absence of a report on VirusTotal does not necessarily mean that the
IP is benign. However, a listed IP address is most likely malicious, since
VirusTotal as most blacklist sites require a high threshold of confidence for
blacklisting an address. This way, we find in total 688 malicious IP addresses
for our forums as shown in Table I.

Using this labeling process we have collected all the IP addresses that have
appeared on our forums prior to their report on VirusTotal. For building our
model, we also randomly select an equal number of IP addresses that have not
been reported as malicious and via manual inspection further assess their
status. Finally, for every security forum we have a different dataset and
hence, we build a different model.

(a) Wilders Security.

(b) Offensive Community.

(c) Ashiyane

Figure 1: CCDF of the number of posts per user ($\log$-$\log$ scale).

(a) Wilders Security

(b) Offensive Community

(c) Ashiyane

Figure 2: CCDF of the number of thread per user ($\log$-$\log$ scale).

(a) Wilders Security

(b) Offensive Community

(c) Ashiyane

Figure 3: CCDF of the number of IP addresses per post ($\log$-$\log$ scale).

##  III InferIP: Malicious IP Detection

We propose a method to identify whether an IP address within a post is
malicious. For example, although many users report a malicious IP address,
such as one that is attacking the user’s network, there are also users that
will mention a benign IP address when people discuss about network tutorials
like setting up Putty or initiating a SSH connection.

While this task is simple for a human, it is non-trivial to automate. Adding
to the challenge, different communities use different terminology and even
different languages altogether (english and farsi in our case). In order to
overcome these challenges, we use a diverse set of features and build a model
to identify IP addresses that are potentially malicious.

Our approach consists of four steps that each hide non-trivial novelties:

Step 1: We consider the user behavior and extract features that profile users
that post IP-reporting posts.

Step 2: We extract keywords from the posts and use information gain to
identify the 100 most informative features.

Step 3: We identify meaningful latent feature sets using an unsupervised co-
clustering approach [19].

Step 4: We train a classifier using these latent feature sets using 10-fold
cross validation.

We describe each step in more detail.

Step 1: Behavioral Features. We associate each user of the forum with a set of
11 features that capture their behavior. In particular:

  * •

Number of posts; the total number of posts made by the user

  * •

Number of threads; the total number of threads the user has contributed to

  * •

Number of threads initiated; the total number of threads initiated by the user

  * •

Average thread entropy; the average entropy of the user distribution of the
threads in which the user has contributed to

  * •

Number of active days; the number of days that the user generates at least one
post

  * •

Average day entropy; the average entropy of the user distribution of the posts
made on the days that the user is active

  * •

Active lifetime; the number of days between the first and the last post of the
user

  * •

Wait time; the number of days passed between the day the user joined the forum
and the day the user contributed their first post

  * •

Average post length; the average number of characters in the user’s posts

  * •

Median post length; the median number of characters in the user’s posts

  * •

Maximum post length; the number of character’s in the user’s longest post

Step 2: Contextual Features.  Apart from the aforementioned behavioral
features we also include features related with the context in which an IP
address appears within a post. In particular, we consider the frequency of the
words (except stop-words) in the posts. Words that are frequent only in few
documents (posts in our case) are more informative than those that appear
frequently on a larger corpus [21]. To this end, we use TF-IDF to weight the
various words/terms that appear in our data. After calculating the frequency
and the corresponding weights of each word in the dataset we end up with more
than 10,000 features/terms. Hence, in the next step we select discriminative
features by extracting latent features.

We begin by performing feature selection in order to identify the most
informative features by applying the information gain framework [25].
Furthermore, in order to avoid overfitting we pick a random subset of posts
from the whole dataset and select the highest ranked features based on
Information Gain score. In this way, a subset of discriminative keywords, 100
in our model, are selected. It turns out that each user uses only a small
number of those words, resulting in a sparse dataset which we wish to exploit
in our model.

TABLE III: Selecting a classifier: overall accuracy. Forum | Naive Bayes | 3NN | Logistic regression
---|---|---|---
Wilders Security | 91.9% | 87.1 % | 94.8%
Offensive Comm. | 84.1% | 83.2% | 86.5%
Ashiyane | 85.1% | 82.3% | 94%
TABLE IV: InferIP evaluation: 10-fold cross validation evaluation (using Logistic Regression). Forum | Instances | Precision | Recall | ROC Area
---|---|---|---|---
Wilders Security | 362 | 0.9 | 0.94 | 0.96
Offensive Comm. | 342 | 0.88 | 0.85 | 0.91
Ashiyane | 446 | 0.9 | 0.92 | 0.92

Step 3: Identifying latent feature sets. We also like to leverage latent
similarities of different posts in some of the dimensions spanned by post
features and behavioral features for the writer of the post. Essentially, we
seek to identify groups of highly similar posts under a small number of
features, which does not necessarily span the full set of features. The reason
why we wish to pinpoint a subset of the features instead of the entire set is
because this way we are able to detect subtle patterns that may go undetected
if we require post similarity across all the features. We call those sets of
feastures latent feature sets . To this end, we apply a soft co-clustering
method, Sparse Matrix Regression (SMR) [19], to exploit the sparsity and
extract latent features of the post containing IP addresses. Given a matrix
$\mathbf{X}$ of posts $\times$ features, its soft co-clustering via SMR can be
posed as the following optimization problem:

$\min_{\mathbf{a}_{r}\geq 0,\mathbf{b}_{r}\geq
0}\|\mathbf{X}-\sum_{r}^{R}\mathbf{a}_{r}\mathbf{b}_{r}^{T}\|_{F}^{2}+\lambda\sum_{i,r}|\mathbf{a}_{r}(i)|+\\\
\lambda\sum_{j,r}|\mathbf{b}_{r}(j)|$

where $\mathbf{a}_{r}$ and $\mathbf{b}_{r}$ are vectors that “describe” co-
cluster $r$, which we explain below. Each $\mathbf{a}_{r}$ is a vector with as
many dimensions as posts. Each value $\mathbf{a}_{r}(i)$ expresses whether
post $i$ is affiliated with co-cluster $r$. Similarly, $\mathbf{b}_{r}$ is a
vector with as many dimensions as features, and $\mathbf{b}_{r}(j)$ expresses
whether feature $j$ is affiliated with with co-cluster $r$. Parameter
$\lambda$ controls how sparse the co-cluster assignments are, effectively
controlling the co-cluster size. As we increase $\lambda$ we get sparser
results, hence cleaner co-clustering assignments. We tune $\lambda$ via trial-
and-error so that we obtain clean but non-empty co-clusters, and we select
$\lambda=0.01$ in our case.

Step 4: Training the model. We subsequently train a number of classifiers
using the selected features based on $\mathbf{a}$ matrix. In particular, we
examine (a) a Naive Bayes classifier, (b) a K-Nearest Neighbor classifier and
(c) a logistic regression classifier. Our 10-fold cross validation indicates
that the Logistic regression classifier outperforms kNN and Naive Bayse,
achieving high accuracy, precision and recall (see Table III).

Determining feature sets. We investigate the effect of selecting different
feature sets in classifying IP addresses in forums. To this end, we
investigate three subsets of the features discussed earlier.

a. Words-Frequency is the normalized frequency of the most informative words
that appear in a post as discussed in Step 2.

b. Combined is the set of features which consists of the combination of the
words frequency features, defined above, and user behaviour features, which
are extracted in Step 1. In other words, it is the union of the features in
Step 1 and Step 2.

c. Co-Clustered is the latent set of features extracted in Step 3 by applying
the co-clustering approach on the Combined features set.

We evaluate these three sets of features on their ability to enable the
classification. In more detail, we use these features with a classifier to
assess their effectiveness by computing the accuracy of the classifier to
identify malicious IP addresses. According to the results which are shown in
Figure 4, the Co-Clustered features set exhibits higher accuracy by 4.1%
compared to Words-Frequency. On the other hand, although the Combined features
do not increase the accuracy compared to the Words-Frequency, the co-
clustering method does. It extracts the latent features from the Combined
features set and outperforms Words-Frequency and Combined in identifying
malicious IP addresses.

Figure 4: Accuracy of different feature sets in Wilders Security forum to
detect malicious IP

###  III-A Applying InferIP on the forums

Having established the statistical confidence of our classifier, we apply it
on the posts of the forums except the ones that we used in our groundtruth. We
use the logistic regression classifier as it exhibits the best performance.

Applying InferIP on the forums shows that there is a wealth of information
that we can extract from security forums in two aspects of the quantity and
time of detecting malicious IP against VirusTotal.

a. Detecting more IP addresses. With InferIP, we find an additional 670
malicious IP addresses in Wilders Security, and 617 in Offensive Community 806
in Ashiyane (see Table I). In other words, InferIP enables us to find three
times additional malicious IP addresses in total compared to the IP addresses
found on VirusTotal. It is interesting to observe that this factor varies
among our three sites. For Ashiyane, our method finds roughly 6 times
additional malicious IP addresses. With a precision of roughly around 90% and
considering small amount of False Positive rate, our method can add a
significant number of malicious IP addresses to a blacklist. Using the limited
manual inspection, we confirm that the precision of the method on out of
sample data is in the order of 88%.

b. Detecting malicious IP addresses earlier: more than half IPs, at least 3
months earlier Here we focus on the malicious IP addresses that are jointly
identified by our method and VirusTotal and compare the time that they were
reported in each source, and show the results in Table V for 3, 6 and 12
months difference in time. We compare jointly detected IP addresses with
InferIP and VirusTotal in terms of time that the IP addresses were mentioned
in posts and the time they were reported on VirusTotal. We see that on average
62% of the malicious IP addresses with InferIP could be identified at least 3
months earlier than VirusTotal. We can see that with InferIP, we find 53%, 71%
and 62% of these IP addresses in Wilders Security, Offensive Community and
Ashiyane respectively at least 3 months earlier than in VirusTotal. We also
identify 39% and 24% of the malicious IP addresses respectively at least 6 and
12 months earlier with InferIP.

Additional stress-testing of our accuracy: In order to assess the performance
of our approach, we randomly picked 10 percent of the labeled data with
InferIP method and annotated them manually by human annotators. The calculated
accuracy on the sampled data shows more than 85% accuracy on average over all
datasets which is close but somewhat lower than the reported accuracy in the
Table III.

(a) Wilders Security

(b) Offensive Community

(c) Ashiyane

Figure 5: CCDF of the number of overall posts per Contributing users (who report malicious IPs) in $\log$-$\log$ scale. TABLE V: Timely comparison between jointly detected malicious IP addresses in InferIP and VirusTotal. Reported percentage of malicious IP Addresses which InferIP detected earlier than VirusTotal  | At least X months earlier
---|---
Dataset | 3 | 6 | 12
Wilders Security | 53% | 23% | 14%
Offensive Community | 71% | 46% | 21%
Ashiyane | 62% | 49% | 37%
Average (across forums) | 62% | 39% | 24%

Contributing Users. Who are the users that report malicious IP addresses? We
want to understand and ideally, develop a profile for these users, which we
will refer to as Contributing users. We start by considering the number of
post these users post on the forums.

The majority of IP reporting is done by highly active (more than 10 posts
overall) in Ashiyane. In Figure 5, we show the cumulative complementary
distribution function for the number of posts per Contributing user for
Ashiyane. More than 72% of the Contributing users post more than 10 posts
overall, which we consider as high engagement given the distribution of
posting that we saw in the previous section. Therefore, in Ashiyane,
Contributing users are contributing significantly in reporting malicious IP
addresses. Intrigued, we examined further and found that, among them, there
are two users who have more than 1000 posts, 1058 and 2780 to be exact, and
whose user-names are "Classic" and "Crisis". On the other side of the
spectrum, 2.4% of Contributing users have posted a single post in the forum,
and in that post they reported a malicious IP address.

The majority of IP reporting is done by less active users (less than 10 posts
overall) in Offensive Community. In Figure 5, we show the cumulative
complementary distribution function for the number of posts per Contributing
user for Offensive Community. Unlike Ashiyane, here 65% of the Contributing
users have less than 10 posts overall. Going into more detail, roughly 12% of
the Contributing users have a single post overall, while 26% of them have only
two overall posts. The same behavior is observed in Wilders Security which is
shown in Figure 5.

Overall, there does not seem to be an obvious pattern between number of total
posts and number of malicious IPs reported among Contributing users.

###  III-B Case-study: from reported malicious IPs to a DDoS attack

We show that mining the forums could actually provide information about real
events. We identify a link between a malicious IP address that our method
detected with an actual DDoS attack.

We conducted the following analysis. We plot the time-series of the number of
posts containing malicious IP addresses in Wilders Security from 2012 to 2013
found by InferIP. We show the time-series in Figure 6. We observe some spikes
on these time-series, which we further analyze. One of the spikes was in
September 2012, and it reports a set of malicious IP addresses that were
involved in an DDoS attack that month. That same thread continued being
active, and in December of 2012, it was reported in that thread that attack
was caused by Nitol Botnet due to a Microsoft’s vulnerability [3].

We argue that this case-study points to additional layers of functionality
that can be built upon our method, that can provide a semi-automated way to
extract richer information beyond just reporting malicious IP addresses.

Figure 6: Time-series of the number of posts containing malicious IP reported
in each month for Wilders Security.

###  III-C Discussion and limitations

Although our method exhibits pretty good accuracy overall, we attempt to
understand its limitations and detect the source of misclassifications.

Limited text in the post: The words in the post provide significant evidence
for the classification. In some cases, some posts are very sparse in their
text, which makes the classification of the included IP address harder. We
consider these kinds of posts a significant contributor to misclassifications.

Characterization at the post level: In our method, we classify an IP address
by using features at the level of a post. Recall that roughly 86% of all posts
across all forums has a single IP per post as shown in Figure 3. In other
words, having more than one IP address per post is already not very common.
Furthermore, even more rarely, we have seen a few cases, where a post contains
both a benign and a malicious IP address. As our method is currently set-up,
this will lead to errors in the classification. A straightforward solution is
to consider examining the text surrounding each IP address within the post.

##  IV  SpatioTemporal Analysis

In this section, we discuss the spatiotemporal features of the malicious IP
addresses identified in security forums in Section III.

###  IV-A Temporal analysis

The key question from a temporal point of view is if the number of reported
malicious IP addresses increases or decreases over time.

Figure 7: Increasing trend: Malicious IP addresses reported on the forums each
year.

The number of reported malicious IP addresses has increased by a factor 8 in 4
four years. In Figure 7, we plot the number of reported malicious IPs found by
our method across all three forums between 2011-2016. We find that the number
increased by a factor of 8: from roughly 100 to roughly 800. In spite of some
decreases in years 2011, 2012 and 2015, it has a clear increasing trend.

###  IV-B Spatial analysis

We study the geo-location of the identified IP addresses from Section III. We
utilize GeoLite database [2], which can show us the country and continent of
an IP address. Here we focus on continents of the IP addresses location.

A natural question to ask is whether the geographical distribution of the
malicious addresses differs between VirusTotal and InferIP. We investigate
this in detail below.

VirusTotal: North America hosts the majority of the reported malicious IP
addresses. We plot the percentage of the distribution of the IP addresses
extracted from VirusTotal across continents in Figure 8 (a) between 2011-2016.
We observe that the majority of the malicious IP addresses are located in the
North America continent. There are two exception in 2013 and 2016 when Asia
and Europe respectively contain most of the malicious IP addresses. Overall,
Table VI shows the geo-graphical distribution over all the years: North
America, Asia and Europe are the three most active continents in that order.

InferIP: North America dominates again, but South America and Africa have non-
trivial contributions. We plot the percentage of the distribution of the IP
addresses extracted form InferIP across continents in Figure 8 (b) between
2011-2016. We observe that North America hosts the majority of the reported
malicious IP addresses again, but we find a more diverse global activity
compared to what we observed in VirusTotal. For example, we can see that in
years 2013, 2014, and 2016: (a) Asia has the majority of the malicious IP
addresses, and (b) South America and Africa have a considerable percentage of
malicious IP addresses. However, when seen across all years, the geographical
distributions of the IPs in InferIP and VirusTotal quite similar: North
America, Asia and Europe have the majority of the malicious IPs detected by
InferIP similarly to those of VirusTotal. In Figure 9, we plot the
geographical distribution of malicious IPs per continent across all years and
all forums for InferIP and VirusTotal, while the exact numbers are shown in
Table VI. Qualitatively the distributions look relatively similar, especially
in the order of significance of the continents, but at the same, we can see
that South America and Africa have a larger percentage of IP addresses in
InferIP compared to those in VirusTotal.

(a) VirusTotal

(b)InferIP

Figure 8: SpatioTemporal distribution of malicious IP addresses detected by InferIP and VT . TABLE VI: Percentage of distribution of IP addresses across continents over all the years. | North America | Asia | Europe | South America | Africa | Oceania
---|---|---|---|---|---|---
InferIP | 46.7 | 32.5 | 13.5 | 5.2 | 1.6 | 0.5
VirusTotal | 50 | 26.5 | 20.4 | 2.4 | 0.6 | 0.17
Figure 9: The percentage distribution of malicious IP Addresses in each
continent across all three forums for InferIP and VirusTotal.

##  V Related Work

We briefly discuss three categories of relevant research.

a. Analyzing structured security sources. There is a long line of research
studying the ontology of cyber security and the automatic extraction of
information from structured security documents. Iannacone et al.[16] developed
a schema for extracting relevant concepts from various types of structured
data sources. In another work, Blanco et al. [9] proposed methods to detect
anomalies on the extracted ontology and network flow graph. Moreover, Bridges
et al.[10] proposed a method to do entity labeling on structured data by
utilizing neural networks. These work are complementary to ours as we focus on
unstructured data, which poses different challenges.

b. Analyzing online security forums. Recently security forums have been the
focus of various studies that showcase the usefulness of the information
present in security forums. For example, Motoyama et al. [18] present a
comprehensive statistical analysis in underground forums. Others studies focus
on the users’ classification or the discovery of the relationships between the
forum’s members [26, 7]. Extracting different discussion topic in the forums
and classifying the language of the codes posted in the forum has been done in
[23]. Contrary to these studies, our work emphasizes on the development of
automated systems that actually exploit the wealth of information in these
security forums in order to enhance security. Similar to detecting malicious
users on commenting platforms has been done on [17]. A recent work analyzes
security forums to identify and geo-locate Canadian IP addresses focusing on
spam and phishing [13] and in another work, Portnoff et al. [20] studies the
exchange of malicious services and tools and studies their prices on the
security forums.

c. Analyzing blogs and social networks. There has been a plethora of studies
on blogs and social media, but their goals are typical not related to
extracting security information. [11, 8, 24]. The studies range from modeling
user behavior [12, 22] to inferring information about the user (demographics,
preferences, mental state), and to modeling the information propagation on
online forums. Although interesting, the focus of these studies are
significantly different from our goal here.

##  VI Conclusion

The take away message from our work is that there seems to be a wealth of
useful information in security forums. The challenge is that the information
is unstructured and we need novel methods to extract it. In this direction, a
key insight of our work is that using behavioral and text-based features can
provide promising results.

In support of this assertion, we develop a systematic method to extract
malicious IP addresses reported in security forums. We utilize both
behavioral, as well as textual features and show that we can detect malicious
IP addresses with high accuracy, precision and recall. Our results in Table I
are promising.

We then apply InferIP to all the posts we have collected. Although are
classification is not perfect, our relatively high precision (hovering around
90% in Table IV) provides sufficient confidence in our results. We find three
times as many additional malicious IP addresses as the original malicious IP
addresses identified by VirusTotal. Furthermore, even for the jointly
discovered IP addresses, at least 53% of the IP addresses detected at least 3
months earlier than VirusTotal. The key message from our spatiotemporal
analysis is that the number of reported malicious IP addresses is increasing
over time.

In the future, we plan to extend our work by extracting other types of
security information. Our first goal is to detect malicious URLs mentioned in
the forums. Our second and more ambitious goal is to identify the emergence of
new malware, threats, and possibly attacks, which we expect to see associated
with large numbers of panic-filled or help-requesting posts. Our final goal is
to identify malicious users, since interestingly, some users seem to be
promoting and selling hacking tools in these forums.

##  VII Acknowledgments

This material is based upon work supported by an Adobe Data Science Research
Faculty Award, and DHS ST Cyber Security (DDoSD) HSHQDC-14-R-B00017 grant. Any
opinions, findings, and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views
of the funding institutions.

## References

  * [1] Ashiyane.  http://www.ashiyane.org/forums/.
  * [2] Geolite.  http://dev.maxmind.com/geoip/legacy/geolite/.
  * [3] Nitol-botnet.  https://threatpost.com/tag/nitol-botnet/.
  * [4] Offensive community.  http://www.offensivecommunity.net.
  * [5] Virustotal.  http://www.virustotal.com.
  * [6] Wilders security.  http://www.wilderssecurity.com.
  * [7] A. Abbasi, W. Li, V. Benjamin, S. Hu, and H. Chen.  Descriptive analytics: Examining expert hackers in web forums.  In 2014 IEEE Joint Intelligence and Security Informatics Conference, pages 56–63, Sept 2014.
  * [8] T. Althoff, P. Jindal, and J. Leskovec.  Online actions with offline impact: How online social networks influence online and offline user behavior.  In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM ’17, pages 537–546, New York, NY, USA, 2017. ACM.
  * [9] C. Blanco, J. Lasheras, R. Valencia-García, E. Fernández-Medina, A. Toval, and M. Piattini.  A systematic review and comparison of security ontologies.  In 2008 Third International Conference on Availability, Reliability and Security, pages 813–820, March 2008.
  * [10] R. A. Bridges, C. L. Jones, M. D. Iannacone, and J. R. Goodall.  Automatic labeling for entity extraction in cyber security.  CoRR, abs/1308.4941, 2013.
  * [11] J. Cheng, M. Bernstein, C. Danescu-Niculescu-Mizil, and J. Leskovec.  Anyone Can Become a Troll: Causes of Trolling Behavior in Online Discussions.  ArXiv e-prints, Feb. 2017.
  * [12] P. Devineni, D. Koutra, M. Faloutsos, and C. Faloutsos.  If walls could talk: Patterns and anomalies in facebook wallposts.  In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015, ASONAM ’15, pages 367–374, New York, NY, USA, 2015. ACM.
  * [13] R. Frank, M. Macdonald, and B. Monk.  Location, location, location: Mapping potential canadian targets in online hacker discussion forums.  EISIC ’16, 2016.
  * [14] J. Gharibshah, T. C. Li, M. S. Vanrell, A. Castro, K. Pelechrinis, E. E. Papalexakis, and M. Faloutsos.  Inferip: Extracting actionable information from security discussion forums.  In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, ASONAM ’17, pages 301–304, New York, NY, USA, 2017. ACM.
  * [15] H. Hang, A. Bashir, M. Faloutsos, C. Faloutsos, and T. Dumitras.  “Infect-me-not": A user-centric and site-centric study of web-based malware.  In IFIP Networking, pages 234–242, May 2016.
  * [16] M. Iannacone, S. Bohn, G. Nakamura, J. Gerth, K. Huffer, R. Bridges, E. Ferragut, and J. Goodall.  Developing an ontology for cyber security knowledge graphs.  In Proceedings of the 10th Annual Cyber and Information Security Research Conference, CISR ’15, pages 12:1–12:4, New York, NY, USA, 2015. ACM.
  * [17] T. C. Li, J. Gharibshah, E. E. Papalexakis, and M. Faloutsos.  Trollspot: Detecting misbehavior in commenting platforms.  In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, ASONAM ’17, 2017.
  * [18] M. Motoyama, D. McCoy, K. Levchenko, S. Savage, and G. M. Voelker.  An analysis of underground forums.  In Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, IMC ’11, pages 71–80, New York, NY, USA, 2011. ACM.
  * [19] E. E. Papalexakis, N. D. Sidiropoulos, and R. Bro.  From k-means to higher-way co-clustering: Multilinear decomposition with sparse latent factors.  IEEE transactions on signal processing, 61(2):493–506, 2013.
  * [20] R. S. Portnoff, S. Afroz, G. Durrett, J. K. Kummerfeld, T. Berg-Kirkpatrick, D. McCoy, K. Levchenko, and V. Paxson.  Tools for automated analysis of cybercriminal markets.  WWW ’17, 2017.
  * [21] J. Ramos.  Using TF-IDF to determine word relevance in document queries.  In Instructional Conference on Machine Learning, 2003.
  * [22] R. Rawassizadeh, E. Momeni, C. Dobbins, J. Gharibshah, and M. Pazzani.  Scalable daily human behavioral pattern mining from multivariate temporal data.  IEEE Transactions on Knowledge and Data Engineering, 28(11):3098–3112, Nov 2016.
  * [23] S. Samtani, R. Chinn, and H. Chen.  Exploring hacker assets in underground forums.  In IEEE International Conference on Intelligence and Security Informatics (ISI), pages 31–36, May 2015.
  * [24] J. Ugander, B. Karrer, L. Backstrom, and C. Marlow.  The anatomy of the facebook social graph.  CoRR, abs/1111.4503, 2011.
  * [25] Y. Yang and J. O. Pedersen.  A comparative study on feature selection in text categorization.  In Proceedings of the Fourteenth International Conference on Machine Learning, ICML ’97, pages 412–420, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc.
  * [26] X. Zhang, A. Tsang, W. T. Yue, and M. Chau.  The classification of hackers by knowledge exchange behaviors.  Information Systems Frontiers, 17(6):1239–1251, Dec. 2015.