Cory Thoma
email: corythoma@cs.pitt.edu

Alexandros Labrinidis
email: labrinid@cs.pitt.edu

Adam J Lee
email: adamlee@cs.pitt.edu

Shoal: Query Optimization and Operator Placement for Access Controlled Stream Processing Systems

Distributed Data Stream Processing Systems (DDSPS) execute on transient data flowing through long-running, continuous, streaming queries, grouped together in query networks. Often, these continuous queries are outsourced by the querier to third-party computing platforms to help control the cost and maintenance associated with owning and operating such systems. Such outsourcing, however, may be contradictory to a data provider's access controls as they may not permit their data to be viewed or accessed by an unintended third party. A data provider's access controls may, therefore, prevent a querier from fully outsourcing their query. Current research in this space has provided alternative access control techniques that involve computation-enabling encryption techniques, specialized hardware, or specialized query operators that allow for a data provider to enforce access controls while still allowing a querier to employ a third-party system. However, no system considers access controls and their enforcement as part of the query optimization step. In this paper, we present Shoal, an optimizer that considers access controls as first class citizens when optimizing and distributing a network of query operators. We show that Shoal can generate more efficient queries versus the state-of-the-art, as well as detail how changes in access controls can generate new query plans at runtime.

Introduction

The ever-increasing and ever-changing size, speed, and availability of accessible data has led to the rise of new outsourced data processing paradigms. One such paradigm is Data Stream Processing handled by Distributed Data Stream Processing Systems (DDSPSs). A DDSPS handles data on-the-fly by executing on transient data with longrunning continuous computations (queries), such as streaming operations, map-reduce functions, or user-defined functions, etc. These computations are often outsourced to third-party systems that handle data processing and execution.

Outsourcing computation is desirable for the querier as it provides them with cost savings. For instance, the querier need not maintain expensive hardware and software platforms. Further, the cloud provider offers guarantees on uptime and service availability that a querier can rely on. Finally, the querier can take advantage of a cloud provider's ability to scale to meet demand, by allocating new resources or freeing up underused ones. When a querier contracts a third-party cloud service provider, they are often able to optimize their query to take advantage of different third-party offerings and pricing models. In doing so, they are able to improve the efficiency of their query for some measurable metric (e.g., latency, throughput, monetary cost) by taking advantage of location, current pricing, current load, and other factors at runtime by changing the placement of certain components (i.e., operators) of their queries. This allows queriers to freely move queries around to improve some aspect of the query's performance.

When a data provider dictates access controls over their streaming data, however, a querier may lose some of these freedoms. For instance, if a data provider authors an access control policy that removes a third-party altogether, the querier would lose the ability to execute any part of their streaming query on that provider. Similarly, if access controls are enforced using some cryptographic method (e.g., Polystream [START_REF] Thoma | Polystream: Cryptographically enforced access controls for outsourced data stream processing[END_REF] or Streamforce [START_REF] Anh | Streamforce: outsourcing access control enforcement for stream data to the clouds[END_REF]), the querier may experience degraded performance as different permissions require different encryption schemes, each incurring different overheads. In both cases, a querier stands to lose some of the benefits of hosting their queries on a third-party system, and may even be required to host the query themselves.

Queriers must consider access controls when trying to generate and optimize their queries. For instance, when a query is broken down into different operators, some operators may be able to execute directly on plaintext, but may have to execute on a queriermaintained machine, whereas others may be more costly (monetarily, in terms of latency, or otherwise) but can be executed on a third-party system. A querier must now be able to reason about and decide which implementation of an operation to choose given the accesses they have been provided. This implies that a querier must be able to enumerate potential operators and consider them at query optimization time to ensure that the most efficient query plan is derived given each data providers' access controls. Further, when a data provider changes their access controls, query networks may need to be updated.

Currently, DDSPS optimizers and related work have explored DDSPSs optimization in a limited scope. Some have simply focused on better utilization of the underlying computation hardware alone [START_REF] Huang | Operator placement with qos constraints for distributed stream processing[END_REF], while others have focused on the underlying network alone [START_REF] Backman | Managing parallelism for stream processing in the cloud[END_REF][START_REF] Chatzistergiou | Fast heuristics for near-optimal task allocation in data stream processing over clusters[END_REF][START_REF] Rizou | Solving the multi-operator placement problem in large-scale operator networks[END_REF][START_REF] Srivastava | Operator placement for in-network stream query processing[END_REF]. Several optimizers and systems have focused on the impact of data variability on the system in the presence of access controls [START_REF] Anh | Streamforce: outsourcing access control enforcement for stream data to the clouds[END_REF][START_REF] Thoma | Polystream: Cryptographically enforced access controls for outsourced data stream processing[END_REF] and in the impact of data stream rates and selectivities [START_REF] Abadi | The design of the borealis stream processing engine[END_REF][START_REF] Arasu | Stream: The stanford data stream management system[END_REF]. Currently, there is no system that focuses on optimizing queries based on the underlying access controls from different data-providers. Further, the closest related work focuses on the use of an optimize-thenplace approach in which a user's query is first optimized for non-distributed execution and then post-processed for placement on distributed resources. Finally, related work with enforcing access controls in a DDSPS focuses on a single query, which may not suit a querier as they may query many data providers.

We present an optimizer that considers a querier's access privileges at optimization time to produce a high-quality placement and ordering of individual streaming operators. Our proposal, Shoal, 1 uses a dynamic programming algorithm to guarantee optimal placement and orderings for moderate-sized sets of streaming queries on a DDSPS, and includes a heuristic approach for larger query networks. Shoal combines the ordering and placement steps to take advantage of the underlying system by considering multiple orderings on various distributed computation infrastructures, and avoids the pitfalls of the optimize-then-place approach. To this end, we make the following contributions:

• We show the optimize-then-place approach to be a sub-optimal approach for computing operator placement in a DDSPS. • We introduce the first cost model for distributed streaming queries that leverages parallelism inherent to the DDSPS and accounts for key sources of heterogeneity such as fluctuations and changes in the underlying data streams and the underlying system and network. • We detail an optimization algorithm that can execute both at query initialization as well as when a change in the system is detected. This algorithm only optimizes the parts of any queries that are potentially affected by a change in access controls. By only considering parts that are affected by system changes, this online algorithm is able to quickly re-optimize and recover while maintaining an optimal solution. • We run an extensive evaluation of our algorithms and compare to several baseline, state-of-the-art, and optimize-then-place algorithms. We show that our proposed framework can produce higher quality optimization and placement plans (up to 2.2x better) with reasonably low overheads, and further show these plans are of a higher quality when compared to related work.

The remainder of this paper is organized as follows. We present the system model in Section 2 and formalize our problem statement in Section 3. We describe our proposed approach in Section 4 and present results form our experimental evaluation in Section 5. Section 6 summarizes related work. We conclude in Section 7

Background and System Model

This section overview the features Shoal considers when optimizing. We further detail our system model and overview access control frameworks and their affect on a DDSPS.

Background on DDSPSs

Shoal uses a common Distributed Data Stream Processing System (DDSPS) model. DDSPSs separate the data provider from the data consumer, and often separate the data processing machines as well. DDSPSs rely on long running, continuous computations that execute on transient data. Once a DDSPS has processed the transient data, results can be stored or forgotten depending on the computation being done.

DDSPSs can implement many different stream-processing paradigms such as relational data stream processing [START_REF] Abadi | The design of the borealis stream processing engine[END_REF][START_REF] Arasu | Stream: The stanford data stream management system[END_REF][START_REF] Arasu | The cql continuous query language: semantic foundations and query execution[END_REF], MapReduce [START_REF] Lee | Parallel data processing with mapreduce: a survey[END_REF], and user-defined tasks. Relational data stream processing systems use continuous SQL-like queries that are comprised of streaming operations that execute a single task. Similar to traditional database management systems, some operations require large amounts of information to produce their result (e.g., a join or aggregation). Since data is transient in a DDSPS, data is grouped by windows and slides: a window represents how much data to keep (e.g., 100 tuples, 10 minutes, etc.) and a slide represents how often to update the querier (e.g., every 10 seconds, every 500 tuples, etc.).

The system components of a typical DDSPS are listed below.

• Data Providers provide streaming data (subject to access controls) to the system.

• Sites are third-party computational and storage platforms (such as Amazon EC2 or Microsoft Azure). They are tasked with the execution of streaming operations as well as forwarding data. • Data Consumers author and submit streaming queries to the system. These queries can be of a variety of paradigms such as relational streaming continuous queries, map-reduce computations, or user-defined functions.

Access Controls

In a DDSPS, access control enforcement becomes difficult since the data providers can not control the propagation of their data after it is transmitted. The current literature on enforcing access controls in a DSMS can be grouped into two categories: trusted third-party enforcement and untrusted enforcement. Trusted third-party enforcement techniques work by trusting that a computational site will enforce access to their data on their behalf. Such systems either work with special operators [START_REF] Carminati | Enforcing access control over data streams[END_REF][START_REF] Carminati | Specifying access control policies on data streams[END_REF][START_REF] Carminati | A framework to enforce access control over data streams[END_REF] or by re-writing queries [START_REF] Lindner | Securing the borealis data stream engine[END_REF][START_REF] Ng | Privacy preservation in streaming data collection[END_REF] so that access can be limited. Systems that do not trust third-party enforcement will rely on cryptographically enforced access controls. Rather than forcing a querier to process data only after it has been decrypted, systems like PolyStream [START_REF] Thoma | Polystream: Cryptographically enforced access controls for outsourced data stream processing[END_REF] and Streamforce [START_REF] Anh | Streamforce: outsourcing access control enforcement for stream data to the clouds[END_REF] allow the data provider to use specialized computation-enabling encryption techniques to enable thirdparty computation for a querier directly on encrypted data. These systems, however, limit the expressiveness and accessibility of a queriers' potential query. In Streamforce, a querier may only access integer data via a view-like format, (i.e., only allowing filtering and aggregations on numeric data). PolyStream supports a richer set of query operations than Streamforce, but cannot support join or complex user-defined functions over streams from multiple providers. Furthermore, these systems also leak information about the underlying plaintext values, such as equality, relative partial ordering, or relationships between groups of tuples (e.g., the encrypted aggregate of some encrypted data). In either the fully-trusted third-party or the untrusted third-party scenario, access control enforcement comes with computational overheads that must be properly accounted for when optimizing and placing a query.

Problem Description

In this section, we detail the exact optimization problem addressed by our framework and define the different components of a Distributed Data Stream Processing System (DDSPS). We offer a description of our optimization approach and show the optimizethen-place approach to be suboptimal.

Problem Description

In order to properly define the problem being addressed here, we must first formalize the required components. There are three main components to optimizing and placing a data consumer's computation: sites, operations, queries, and query networks. Definition 1. Site: As introduced in Section 2, a site s executes operators. Interconnections between sites have bandwidth (in bits/s, where tuples can be of varying size) and latency (in ms) characteristics that we represent as b(s 1 , s 2 ) and l(s 1 , s 2 ) respectively. Sites are associated with the following properties: • s.cap is the site's processing capacity (in cycles, translated to tuples/s).

• s.name is the site's name used for unique identification purposes.

• s.per is a set of permissions {< o, f >| site s can execute a physical operator o on field f }.

Definition 2. Operation: An operation op is a set of operators that execute the same task via different physical implementations.

• op.type represents the action to be performed on a data stream (e.g., filter, projection, summation, top-k, etc.). • op.args includes metadata about the operations such as the join condition or selection criteria. • op.input represents the set of fields required for this operation to execute.

• op.output represents the set of fields in the output of this operation.

• op.id is a unique identifier for the operation.

A typical operation can be a filter over someone's age, a join to match two streams, or an aggregation to find the maximum profit in a given window of time. Operations can be implemented using different techniques, represented as operators.

Definition 3. Operator: The basic computational unit used in Shoal is an operator o, which has the following properties: • o.s represents the expected or actual selectivity of the operation. Selectivities can be derived either by estimation, measurements during a warm-up period, or historical selectivity data. • o.c represents the cost of the operation in terms of the latency for computing on one tuple. It can be calculated in a manner similar to the selectivities. • o.site represents the site an operator has been assigned to.

• o.opId represents the ID of the operation (that is to say, the logical operator that this physical operator represents) that this operator implements. • o.window represents the window size for a stateful operator either in tuples or ms, with a default of 0.

Operators allow flexibility when implementing an operation. Consider the potential difference between a hash-join implementation of a join operation versus a merge-join implementation. Given the input rate and selectivity of each stream, it is highly likely that one join would outperform the other in terms of overall latency. An operation would have the merge-join and hash-join as potential operators, and each operator would have a cost that can be used to better optimize the query network. Definition 4. Query: A query is represented as a set q of operations that describe the query or task that a data consumer wishes to execute over a set of data streams.

• leaves(q) returns the set of operations that operate on a raw data stream (i.e., do not require the output of another operation to execute).

Definition 5. Query Network: A query network is represented as a set qn of queries that will execute within the DSMS.

• sinks(qn) returns the set of operations that return a result to a querier (i.e., the last part of any one query).

Using a query, permissions, and a set of available sites as input, Shoal produces a plan as output:

Definition 6. Plan: A plan p = (V o , E o ) where V o is a set of physical operators and E o ⊂ V o ×V o
is the edge set linking the outputs of one operator to the inputs of adjacent operators.

Definition 7. Satisfiability: A plan p satisfies a query network qn if:

• ∀op ∈ qn, ∃! o ∈ V o s.t. o.opId = op.id • ∀o ∈ V o , ∃! op ∈ qn s.t. op.id = o.opId∧ < o, o.metadata >∈ o.site.per • ∀o ∈ p, o.input ⊆ o |<o ,o>∈E o o .out put
That is, each operation in each query that comprises the query network has a unique operator in the plan and that each operator in the plan is the implementation of one operation in the query, and that each operation in the query is represented in the resulting network. Additionally, each operator's input must be part of the output of its immediate predecessor, and each operator must be permitted to execute on its assigned site.

To determine the relative quality of a given plan p, we use the following cost model.

Definition 8. Cost: For a plan p of a Query Network qn, the cost of p, starting at the leaf node(s), is determined by:

max path∈Paths(p) pathCost(path) (1)
where Paths is the set of paths from leaf nodes to sink nodes. The expected input rate for each operator (starting from the initial input rate of the leaf node from the source stream) is:

ir(o i ) = IR qn * ∏ op j ∈pathUpTo(op i ) op j .s (2)
The function pathUpdTo(o) for an operator o is the ordered subset of operators that precede o in the plan (as part of the same query). IR qn is the maximum input rate of any leaf operator on the current path. The cost of a path is:

pathCost(path) = ∑ op i ∈path max(op i .c, op i .window) + Latency(op i , path) * Penalty(o i ) (3) f 3 j 1 f 1 f 2 s 1 f 1 f 2 f 3 j 1 s 1
Selectivity f 1 = .25 f 2 = .96 f 3 = .96 j 1 = .05

Cost: 43

f 3 j 1 f 1 f 2 s 1
Cost: 56

Cost: 36

1 2 3
Fig. 1: Simple continuous query.

The penalty is defined as:

Penalty(o) = 1, if pr(o, o.site) > ir(o i ) ir(o) pr(o,o.site) , otherwise (4)
The function pr(operator, site) determines what the processing rate of a site would be with the operator o assigned to it. If this processing rate is greater than the input rate, then there is no penalty. If the processing rate is insufficient to handle the input rate, the plan is penalized by the input rate over the processing rate. Latency is computed as:

Latency(o, path) = 0,
for o ∈ leaves(qn) l(op, op i-1 ), for op i>1 [START_REF] Arasu | The cql continuous query language: semantic foundations and query execution[END_REF] Constrained by s.cap and bandwidth(op i , op i-1 ).

Definition 9. Problem: Given a query network qn of queries, a set of Sites s, and a set of access control permissions per, produce a plan p that satisfies qn such that Equation 1 is minimized.

Optimize-then-place Approach

A reasonable first step solution to this optimization problem would be to separate optimization from operator placement. This would allow a placement algorithm to simply use an existing off-the-shelf optimizer and post-process the result for placement. This approach, however, can lead to a sub-optimal plan even if the query itself is fully optimized. Consider the following scenario for a continuous query optimizer, which we will use throughout the remainder of the paper to illustrate Shoal: A simple query contains three filters ( f 1 , f 2 , f 3 ), a join ( j 1 ), and a projection (s 1 ) as depicted in the top of Figure 1 as the result of an optimization step. Next consider the three sites available for placement, and assume the network cost is uniform. Each site has a capacity of 10 (unit-less for simplicity). The cost of each filter is 4, of the join 6, and of the project 2; each have selectivities shown in Figure 1. Given these costs, either the join must be co-located with f 1 (the top of Figure 1) or separated from all

27: prunePlans(optPlace[lv])

of f 1 , f 2 and f 3 , (the middle of Figure 1). However, notice that the selectivity of f 1 combined with f 2 is .92, meaning that a tremendous amount of data is being sent over the network to the join. The selectivity of the join, however, is far lower at .05, meaning that a smaller amount of data is being produced. If the query was instead optimized so that f 3 were to follow the join, the overall network cost would be substantially reduced, resulting in a higher quality plan (78.8ms vs. 67.8ms with Equation 1). This illustrates the need for the optimization and placement steps to be considered simultaneously.

The Shoal Optimizer

In this section, we introduce our optimization and placement algorithms.

Online Optimization Approach

Given the long-running nature of continuous queries, there is a high chance (essentially a certainty) that a data provider's access controls will change over time, requiring reoptimization of the network of streaming queries currently deployed. When access controls change for any one data streaming operator, it could possibly have a ripple effect for other downstream operators as they may need to be moved to reallocate resources. To accommodate these changes, there are two possible approaches: stop-the-world and on-the-fly. The stop-the-world approach simply halts query execution and uses Algorithm 1 to re-optimize the query from the root nodes. This approach, however, can lead Algorithm 2 Access Control first-impacted identifier. to large re-optimization times for larger query networks, and can end up doing repetitive work when a relatively small set of operations are affected by the change.

We introduce an on-the-fly approach to mitigate these overheads. The principle behind our on-the-fly approach is to execute Algorithm 1 from the operator that is first affected by the access control update relative to the data providers of the overall query network, which we will call the first-impacted. This requires the ability to determine the first-impacted, which depends upon the type of access control update that occurred.

Access Control Algorithm 2 determines which operators are first-impacted by a change in access controls. It starts by adding operations that directly access raw data streams on Line 2 to the current query network, cld. These operators are then looped through on Line 3, and Line 4 determines if that operator accesses the data being protected by the new access control update. If so, this operation is the first-impacted and the algorithm determines its level by asking the plan for the level. If the operation does not access the protected data, its children are added to the cld set, and it removes itself from this set. This continues until the first-impacted is found. At this point, Algorithm 1 will execute on the descendant children of the first-impacted, as well as all operations at the same level and their descendants. Note that on Lines 16 and 23, we check for all allowable operations. Recall that one physical operation can be implemented by many physical operations (e.g., the querier may have sufficient access to query in plaintext local to their machine and further have access to use a computation-enabling encryption scheme such as an order preserving scheme on encrypted data in the cloud. This function enumerates the possible operators based on the current permissions of the querier. This leaves the already optimized operations and their ancestor operations intact from the previous plan, and re-optimizes the operations at and after the first-impacted's level, leading to less optimization time. The only alteration required for Algorithm 1 is the inclusion of the current plan from which to start, which is simply placed in the optimalPlans set and the Algorithm starts from Line 11 where the level is determined by traversing back to the leaf nodes.

Greedy & Hybrid Approaches

As with traditional dynamic programming optimizers, our algorithm could suffer from prohibitively large execution times for large or complicated query networks (explored further in Section 5). When query networks become too large or complex, we defer to a greedy approach. This approach simply considers one operator at a time and optimally places it. In the base case where each operator needs to be placed, the user defines a time threshold t o f f line for their optimization step. If the dynamic programming approach is expected to exceed t o f f line , then the greedy approach is used. The online approach poses a different problem because there may be uncertainty in how costly an update may be to the system (i.e., the number of operators that need to be re-optimized).

The larger the number of operators that need to be considered, the greater the number of operators requiring re-optimization, and therefore the greater the cost of the update. In a system operating at or near capacity, online updates may end up hindering the quality of the result as some information may be lost during optimization, especially for costly updates on large overall query networks. To combat this problem, we use the greedy approach when updates are too costly relative to the system load. The greedy approach simply re-optimizes, placing each operator in the most optimal location, in a quick but likely non-optimal fashion.

The greedy approach lends itself nicely to distributed systems with heavy load where re-optimization needs to be quick to avoid losing data, but it will not produce plans of the same quality as the dynamic programming approach. To help a data consumer determine which to use, we propose a hybrid solution which automatically determines which approach to use given the current system state. The determination is based on three factors relative to the overall streaming query network submitted by the data provider: (a) buffer capacity, (b) processing time of a single streaming tuple (end-toend), and (c) the input rate. When an update is deemed necessary, its cost c in seconds is determined by multiplying the number of operations needing to be re-optimized by the average amount of time to optimize one operator (based on the execution time of optimizing the entire query, or a running average). Then, the following equation is used to determine which algorithm to use:

uc = ( o∈p ∑ i (b i * t i )) + ir o * c ( 6
)
where o is the operator in the plan p, b i is the utilized buffer size of o, t i is the processing time of o, ir is the input rate. If c < uc then the dynamic programming approach is used, otherwise the greedy approach is used to minimize data loss.

Example

To help illustrate how Shoal optimizes a set of streaming queries, consider the following continuous query on a data stream that contains tuples with a timestamp, company-Name, companyId, and the company profit, as illustrated in Figure 2:

SELECT max(avg_profit), companyName FROM (SELECT companyName, AVG(profit) as avg_profit FROM profitStream GROUP BY companyName EVERY 1m UPDATE 15s;) GROUP BY companyName EVERY 1m UPDATE 15s;

This query requires five operations; a max (m), a projection (p), an average (a), and two group-by operations (g 1 and g 2 ) represented by circles in Figure 2. Assume that the profit field is protected by a homomorphic encryption and the others are plaintext. Further assume (for simplicity) that there are two sites A and B with capacities 10 and 10 respectfully, and a latency of 10ms between them (squares in Figure 2).

Shoal starts with the operation a as it is the operation that accesses raw data. Since a homomorphic option exists for the aggregation, an operator executing a homomorphic scheme is put onto each site and the next round of dynamic programming is initiated. Further, plans are also added for random encryption and trusted machine processing. This aggregation requires a group-by operation, which can execute on the plaintext column for "company name". This operation is placed with the aggregation on each site, making each site's best plan having a cost of 8 which, along with other plans with varying physical operators, are kept for each site. Shoal then tests the remaining operations and determines that the projection p can be added to each site's best plan for a cost of 9. Plans are now kept for each site and for each physical operator, but the minimum plan score is 9. Note that this choice reduces the overall network load by eliminating all columns except the company name and the average. Shoal continues and determines that the maximum operation along with its group-by can not fit on either site and chooses them to operate on site B with site A keeping its previous plan. With all operators placed, the new plan resembles the one in the right half of Figure 2.

Evaluation

To evaluate our optimizers, we decided to use relational continuous queries for the bulk of our experimentation.

Setup: For our evaluation, we limit Shoal to be used in a simple streaming system with data providers, data consumers, and data processing components. For our simulation, data is streamed from a laptop into Amazon AWS EC2 instances. Once data is processed, it is passed back to the laptop to act as the data consumer. We implement the streaming layer on the Apache Storm [START_REF]Storm: Distributed and fault-tolerant realtime computation[END_REF] framework. To keep the streaming layer simple, we use the most basic functionality of Storm where our data provider implements a spout and our data processing nodes implement bolts with no multi-threating or replication (i.e., a bolt just mimics a machine for our purposes). We use Storm only for the transport layer as it guarantees delivery and provides acking and nacking functionality. To simulate real-world streams, each stream is imposed with an artificial latency of 0-30ms to emulate them being geographically separated.

Datasets: We use queries from the TPC-H [START_REF] Poess | New tpc benchmarks for decision support and web commerce[END_REF] workload and modify them for use in a streaming system (e.g., aggregations use windows). We will explicitly call out any changes to the query we made, or if we use more than one query as part of the query network. We further segment data based upon a timestamp so that it is streamed into the system (in a pre-processing step) so that days are equivalent to minutes. All queries are referenced using the query number (e.g., q1 for TPC-H query 1) and the number of operators it translates to (e.g., q1(4) is TPC-H query 1, which has four operations).

Baseline Algorithms: In addition to our original and hybrid dynamic programing algorithms, we chose three additional baselines for comparison: (1) all-on-client, where all of the operations run on one machine, (2) first site, where each operation is placed on the first site available, and switched to the next when either the site is at capacity or there is a conflict with access controls, and (3) greedy, where a plan is generated by greedily assigning each operation based on the best score.

Online Optimizer

This section evaluates our dynamic programing optimizer as compared to other baseline approaches. The cost of an update is based on how many operations in the query network are affected by the update, so we omit cases where the entire network was updated since it would degenerate to the basic case where each operator must be optimized.

Optimization Time Given the cost of an update, this experiment determines the average optimizer execution time for the our dynamic programming approach as well as the baseline approaches.

Configuration: We combine queries in increasing size order (i.e., 1 query, 2 queries, 3 queries, up to 4 queries, or 8, 14, 28, and 45 operators). This provides four data points with an increasing size and number of sinks. All aggregation and join operations are given windows of 5 minutes (to directly use the date field in each relevant tuple). We trigger updates so that only a certain number of operators in each query are affected by the update. Each optimizer is then used to order and place the subsequent operations. Results (Figure 3): Here we can see the dynamic programming approach is the slowest. This optimizer execution time included the time to determine the first-impacted for each approach, for each query. Takeaway: Although Shoal has the highest optimization time, it is still relatively low, especially when executing on a long-running continuous query in a network where the resulting plan quality is much more important.

Plan Quality This experiment evaluates the overall plan quality of each approach in terms of latency (ms) for each updated plans. Again, we present both the expected latency, as well as the actual latency. Here, we include the hybrid approach to show when it may switch optimizers to reduce the overall impact of an update. Configuration: Queries are executed for 10 minutes in total. There is a two-minute window for the initial query, after which an access control update is presented. The query is then updated and the remainder of the time is spent monitoring the updated query. The results presented below are the quality (latency in ms) of the updated query network, as presented by the number of operators updated in the largest network. Results (Figures 5a and5b): Our dynamic programming optimizer produces the best overall latencies for both expected and actual evaluations for the query network. The

Optimization Time (ms)

Operators after frst-impacted DP Greedy Hybrid First Site Fig. 3: Optimizer execution time for the online algorithm approaches. difference between the expected and the actual is roughly 10.2%, which indicates that Shoal can produce results that are close to the actual values. Notice that the hybrid approach chose to switch to the Greedy optimizer in the last update to the query network. This is due to the system being near capacity when the update occurred (roughly 2,500 tuples/s with a processing rate of roughly 2,615 tuples/s), and in the time to process a new query, the system could have lost data, so the hybrid algorithm chose to use the greedy optimizer.

Takeaway: Shoal produces higher quality plans when compared to the baseline. Recovery Time When an update occurs, the system must determine how to reoptimize from first-impacted operation. This process takes time, and while it is processing, the query will still need to be executing. The time between the start of an update optimization and the normal execution of the resulting plan is the time it takes the system to recover from an update. In this experiment, we evaluate this recovery time for access control updates.

Configuration: For this experiment, we generated a 128-operator query network. Operations were selected from a random distribution of operations which included twoway joins, filters, summations, averages, projections, and decrypt-process-encrypt operations. Access control updates occur by specifying a specific change in access controls that target a specific operator such that the update cost remains consistent across the evaluation, and each update causes an increase in latency and a decrease in throughput (i.e., switch from plaintext to encrypted). A query is considered recovered once the latency has normalized back to a steady value.

Results (Figure 4): When an update occurs to an access control policy (Figure 4), the data consumer may lose access as indicated by the unreported latency values. Once the query has been resumed, the larger updates cause a large spike in latency that takes more time to recover from, as expected. Note the processing time of each update also increases, but the recovery time is more-or-less the same (20-30ms). This shows that the new queries can handle the increased workload to make-up for the lost work and then maintain a new latency rather quickly.

Comparison to the State-of-the-Art

We now evaluate the quality of the plans produced by Shoal versus other operator placement approaches, namely Pietzuch et al. [START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF] and Srivastava et al. [START_REF] Srivastava | Operator placement for in-network stream query processing[END_REF].

Algorithms: Pietzuch et al. [START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF] propose a solution that focuses on placing operators in a large-scale distributed network using a latency metric. Their optimizer takes a query plan and places it using a two-step algorithm: first a Virtual Operator Placement step and then a Physical Operator Placement step. The virtual operator placement step considers all operators in a query and places them based on a cost space. This cost space consists of a decentralized view of the network from a single node's perspective and focuses on the latencies between potential sites. There is also a load dimension that can ensure that a single site does not become overwhelmed. Their approach allows for access control updates by allowing operators to migrate between sites. To compare to our work, we fix the cost space by artificially creating latencies and data rates between potential sites (i.e., the assumed information gathered by the DDSMS in their work) and then allow it to adjust over time. The main optimization function used in their work is to minimize the following formula:

∑ l∈L DR(l) * LAT (l) (7)
Where l is the link between two nodes, DR(l) is the data rate of that link, and LAT (l) is the latency of that link. Srivastava et al. [START_REF] Srivastava | Operator placement for in-network stream query processing[END_REF] also reduce data transmission, but do so for localized networks. Their work focuses on using parts of the query itself, as well as the machines available for placement, to make a placement decision. Specifically, they focus on the selectivity of filtering operations, the cost associated with each operation, and the cost associated with sending a tuple through the network. In addition to the above costs, a join's cost is calculated using its selectivity and the cost per unit time for processing one tuple. The cost of a placement plan is therefore the sum of all of the nodes where the selectivities of upstream filters are multiplied by the cost of the current filter. Some filters are correlated and some are not, so the ordering decision comes from the commutative aspect and the overall cost comes from minimizing the cost of the filter and join orderings. To compare with our work, we again assume an artificially created latency and use the same operators' costs and latencies across all approaches.

Configuration: For our comparison, we use multiple queries over a fixed number of sites. We use 5 sites, each connected to each other with an initial latency randomly selected from a range of 5-500 ms. Each query is comprised of between 4 and 128 operations selected as either filters (selection operations) or joins, with plaintext data. Since [START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF] requires an initial query plan, we use Shoal with a single site and sufficient capacity to generate a non-distributed query plan. Finally, each filter is given a selectivity randomly selected from the set {.1,.2,...,.9}. To gather information on actual latencies, each query was executed for a total of five minutes for each approach. Results (Figures 6a &6b): As depicted in Figures 6a and6b, Shoal produces plans with better expected and actual latency. As before, the expected and actual are within an average of 8%, however the Pietzuch et al. approach is more predictable since its expected is on average only 4% different from the actual value. Shoal is able to outperform the other approaches because it attempts to find an optimal solution that takes into account the parallelism inherent to a distributed system by preferring plans that allow work to be done on multiple devices simultaneously. The Pietzuch et al. approach relies on an optimize-then-place approach and missed better filter orderings, which becomes more apparent as queries grow larger. The Srivastava et al. approach does consider ordering, but does not consider the parallelism inherent to a distributed system and would often serialize sets of operations that could have otherwise been done in parallel. Takeaway: By considering ordering and placement at optimization time, as well as taking advantage of parallelization inherent to the distributed system, Shoal can outpreform other state-of-the-art optimizers in terms of end-to-end latency.

Related Work

Stream processing has been rigorously studied in the literature to include novel systems such as Aurora [START_REF] Abadi | Aurora: a new model and architecture for data stream management[END_REF], Borealis [START_REF] Abadi | The design of the borealis stream processing engine[END_REF], and Twitter Herron [START_REF] Kulkarni | Twitter heron: Stream processing at scale[END_REF]. For traditional database applications, the focus for operator placement in distributed database systems usually focuses on replication, sharding, or scalability [START_REF] Cattell | Scalable sql and nosql data stores[END_REF][START_REF] Corbett | Spanner: Google's globally distributed database[END_REF][START_REF] Curino | Relational cloud: A database-as-a-service for the cloud[END_REF][START_REF] Shute | F1: A distributed sql database that scales[END_REF]. The PAQO [START_REF] Farnan | Paqo: Preference-aware query optimization for decentralized database systems[END_REF] optimizer focuses on placing operators in a distributed database system so that one entity does not learn the underlying intension of the query. For data steaming systems, operator placement is of a larger concern since queries are long-running and operators are expected to consume resources for long periods of time while possibly fluctuating in their required resource utilization. The contributions in [START_REF] Cardellini | Optimal operator placement for distributed stream processing applications[END_REF] explore the general problem of operator placement on heterogeneous computational platforms for DDSMs, and propose a linear programming model to place operators. Their approach processes placement in a separate step from optimization, which can lead to suboptimal results (cf. Section 3).

Huang et al. [START_REF] Huang | Operator placement with qos constraints for distributed stream processing[END_REF] fit operators onto sites by calculating the execution time of an operation and place it based on the capacity of each site, using end-to-end delay and throughput as the metrics. Thoma et al. [START_REF] Thoma | Automated operator placement in distributed data stream management systems subject to user constraints[END_REF] place operators in a DDSMS where queriers have the ability to control where operators are placed via a set of constraints. These constraints generally cover all aspects of the placement, but do not consider the access control policies of a data consumer. Operators placement using heuristics to optimize for end-to-end latency and network traffic have also been explored [START_REF] Backman | Managing parallelism for stream processing in the cloud[END_REF][START_REF] Chatzistergiou | Fast heuristics for near-optimal task allocation in data stream processing over clusters[END_REF][START_REF] Rizou | Solving the multi-operator placement problem in large-scale operator networks[END_REF].

Finally, some related work has focused on the impact of enforcing access controls in a DDSPS. Enforcement systems such as FENCE [START_REF] Nehme | A security punctuation framework for enforcing access control on streaming data[END_REF][START_REF] Nehme | Fence: Continuous access control enforcement in dynamic data stream environments[END_REF] include the enforcement overheads in the optimization step by adding streaming operations that can be handled like any other operation, but do so without considering operator placement. Other systems will rewrite queries or alter streaming operators [START_REF] Carminati | Enforcing access control over data streams[END_REF][START_REF] Carminati | Specifying access control policies on data streams[END_REF][START_REF] Carminati | A framework to enforce access control over data streams[END_REF][START_REF] Ng | Privacy preservation in streaming data collection[END_REF], while others focus on protecting a single system, such as Borealis [START_REF] Lindner | Securing the borealis data stream engine[END_REF]. These systems simply explore the overheads associated with access control enforcement and do not consider them at optimization time or during operator placement. Furthermore, these systems do not explore the tradeoff between different types of access control enforcement during optimization time, which is provided in Shoal. Systems like PolyStream [START_REF] Thoma | Polystream: Cryptographically enforced access controls for outsourced data stream processing[END_REF], and Streamforce [START_REF] Anh | Streamforce: outsourcing access control enforcement for stream data to the clouds[END_REF], CryptDB [START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF] consider such tradeoffs, but do either do not operate in a distributed fashion (CryptDB), or do not consider them at optimization time.

Thus far current optimizers and systems have focused on a limited scope of characteristics within a DDSPS, mostly excluding access controls. Either they do not consider optimization and placement simultaneously, or they limit their approach to optimize solely for something like network, hardware, or other traditional metrics. Shoal provides a general cost model and dynamic programming algorithm that accounts for data provider's access control enforcement at query optimization time.

Conclusion

We present Shoal, which considers access controls as first-class-citizens during query optimization. By simultaneously ordering and placing streaming query networks on a per-operator level, Shoal can guarantee optimal results through a dynamic programming algorithm. Further, Shoal reduces optimization time for updates based on changes in access controls by identifying the precise operators that need to be re-optimized and only optimizing from those points forward in an online fashion. Finally, we show that Shoal produces higher quality plans (up to 2.2x) versus the state-of-the-art optimizers, and does so while considering data provider's access controls.

Fig. 2 :

 2 Fig.2: Given a the set of operations and the sites A and B, Shoal optimizes and places the operations so that the first aggregation is placed on A with the projection reducing network load to the second aggregation operation placed on B.

Fig. 4 :

 4 Fig. 4: Recovery time caused by an access control update for different costs.

Fig. 5 :

 5 Fig. 5: Expected and Actual latency for Shoal on random data.

Fig. 6 :

 6 Fig. 6: Expected and Actual latency for Shoal on random data.

  for operation ∈ sc | operation.type = join do 14: for plan1, plan2 ∈ optPlace[lv -1] | (operation.input ⊆ (plan1.out put ∩ plan2.out put)) ∧ operation.opId ∈ plan1.opIds ∧ operation.opId ∈ plan2.opIds do (updateCapacity(plan1, plan2, s) ≥ join.c) ∧ (< join, join.metadata. f ield >∈ s.perms) then 20: for plan ∈ optPlace[lv -1] do 21: for operation ∈ sc | (operation.type = join)∧(operation.opId ∈ plan.opIds) ∧ (operation.input ⊆ plan.out put) do

	Algorithm 1 DynamicProgramming
	1: DynamicProgramming(sc, perms, sites)
	2: optPlace= new Array(ArrayList(plan))
	3: for lea f ∈ leaves(sc) do
	4: optPlace[0] = / 0	Initialize Empty list at level 0
	5: for s ∈ sites do
	6:	for l ∈ operators(lea f ) do
	7:	if s.cap ≥ l.c && (< l, l.metadata. f ield >∈ s.perms) then
	8:	l.site = s
	9:	optPlace[0].add(new plan(l))	Capacity kept per plan
	10: prunePlans(optPlace[0])
	11: for lv = 1...|sc| do
	12: optPlace[lv] = / 0	Initialize Empty list at level lv
	13: 15:	for s ∈ sites do
	16:	for join ∈ allowableOps(operation) do
	17:
	18:	join.site = s
	19:	optPlace[lv].add(joinPlans(plan1, plan2, join))
	22:	for s ∈ sites do
	23:

if for o ∈ allowableOps(operation) do 24: if plan.s.cap ≥ o.c∧ < o, o.metadata. f ield >∈ s.perms then 25: o.site = s 26: optPlace[lv].add(combine(plan, o))

1 :

 1 ACUpdate(Update u, Plan p) 2: cld = sc.lea f

		Operations not processed
	3: for o ∈ cld do
	4: if o.input | u.protectedFields then
	5:	return p.levelO f (o)
	6: else
	7:	cld.add(p.childrenO f (o)
	8: cld.remove(o)

A shoal is a heterogeneous group of fish that is organized to function towards a common purpose, typically of a safety or social nature.

Acknowledgements This work was supported in part by the National Science Foundation under awards CNS-1253204 and CNS-1704139.


Radek Hranický
email: ihranicky@fit.vutbr.cz

Filip Lištiak

Dávid Mikuš

Ondřej Ryšavý
email: rysavy@fit.vutbr.cz

On Practical Aspects of PCFG Password Cracking

Keywords: Password, Cracking, Security, Grammar

When users choose passwords to secure their computers, data, or Internet service accounts, they tend to create passwords that are easy to remember. Probabilistic methods for password cracking profit from this fact, and allow the attackers and forensic investigators to guess user passwords more precisely. In this paper, we present our additions to a technique based on probabilistic context-free grammars. By modification of existing principles, we show how to guess more passwords for the same time, and how to reduce the total number of guesses without significant impact on success rate.

Introduction

Confidential data and user accounts for various systems and services are protected by passwords. Though a password is usually the only piece that separates a potential attacker from accessing the privileged data, users tend to choose weak passwords which are easy to remember [START_REF] Bishop | Improving system security via proactive password checking[END_REF]. In reaction, system administrators and software developers introduce mandatory rules for password composition, e.g., "use at least one special character." While password-creation policies force users to create stronger passwords [START_REF] Proctor | Improving computer security for authentication of users: Influence of proactive password restrictions[END_REF][START_REF] Vu | Improving password security and memorability to protect personal and organizational information[END_REF], recent leaks of credentials from various websites showed the reality is much more bitter. People widely craft passwords from existing words [START_REF] Florencio | A large-scale study of web password habits[END_REF] and often reuse the same password between multiple sites [3]. This fact may be utilized by both malicious attackers and forensic investigators who seek for evidence in password-protected data.

Traditional ways of password cracking contain a brute-force attack where one tries every possible sequence of characters upon a given alphabet, and a dictionary attack where one uses a list of existing passwords and tries each of them. The main drawback of the brute-force attack is the size of a keyspace (a set of all possible password candidates) which grows exponentially with the length of the password, and one does not need to "try everything" to crack the password. The dictionary attack, on the other hand, usually checks a limited number of commonly-used or previously-leaked passwords. It is possible, however, to combine both methods to perform a "smarter" cracking. The use of probability and statistics has been shown to bring substantially better results for cracking human-created passwords [START_REF] Ma | A study of probabilistic password models[END_REF][START_REF] Narayanan | Fast dictionary attacks on passwords using timespace tradeoff[END_REF][START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF].

One approach is the use of Markov chains which consider probabilities that a certain character will follow after another one. The probabilities are learned from an existing password dictionary and then reused for generating password guesses [START_REF] Narayanan | Fast dictionary attacks on passwords using timespace tradeoff[END_REF]. The method, however, only works with individual characters and does not consider digraphs or trigraphs. To work with larger password fragments, Weir et al. proposed the use of probabilistic context-free grammars (PCFG) that can describe the structure of passwords in an existing (training) dictionary. Fragments described by PCFG represent finite sequences of letters, digits, and special characters. Then, by derivation using rewriting rules of the grammar, one can not only generate all passwords from the original dictionary, but produce many new ones that still respect password-creation patterns learned from the dictionary [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF].

The rewriting rules of PCFG have probability values assigned accordingly to the occurrence of fragments in the training dictionary. The probability of each possible password equals the product of probabilities of all rewriting rules used to generate it. Using PCFGs, generating password guesses is deterministic and is performed in an order defined by their probabilities. Therefore, more probable passwords are generated first.

While the creation of such grammar is fast and straightforward, the application of rewriting rules takes a significant amount of processor time, and the number of generated passwords is overwhelming in comparison with the original dictionary. For example, using Weir's tool 1 with a PCFG trained on 6.5 kB elitehacker 2 dataset (895 passwords) generates a 12 MB dictionary with 1.8 million passwords. However, using 73 kB faithwriters dataset (8,347 passwords) generates a 28 GB dictionary with over 3 billion passwords. Even more unpleasant is the time required to generate such datasets. The first 10 and first 100 passwords of darkweb2017 3 dataset and darkweb2017-top100 can be both used for training and generating within 1 minute on Core(TM) i7-7700K CPU. Taking first 1000 passwords requires more than a day to generate guesses on the same processor.

Contribution

Our goal was to make the PCFG-based password cracking utilizable for practical use. We identified factors that influence the time of generating password guesses. Based on Weir's Python PCFG cracker, we created an implementation in Go 4 language, which enables to parallelize the generation of terminal structures making the password generation multiple times faster. Moreover, we proposed methods that remove specific rewriting rules from the grammar which leads to a massive speedup of password guessing and allows the process to end in a meaningful time without having a considerable impact on success rate.

Structure of the paper

The paper is structured as follows. Section 2 provides an introduction to PCFG and discusses related work. Section 3 describes the enhancements we made to PCFG-based techniques, while Section 4 shows experimental results of our work. Finally, Section 5 concludes the paper.

Background and related work

For a long time, probability and statistics have been applied to measure password strength [START_REF] Kelley | Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms[END_REF][START_REF] Proctor | Improving computer security for authentication of users: Influence of proactive password restrictions[END_REF][START_REF] Vu | Improving password security and memorability to protect personal and organizational information[END_REF] and generate guesses in password cracking [START_REF] Houshmand | Next gen pcfg password cracking[END_REF][START_REF] Ma | A study of probabilistic password models[END_REF][START_REF] Narayanan | Fast dictionary attacks on passwords using timespace tradeoff[END_REF][START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF]. Major password leaks allowed to make a clearer image of how user create their passwords [START_REF] Bonneau | The science of guessing: Analyzing an anonymized corpus of 70 million passwords[END_REF]. Such knowledge has been utilized in multiple password cracking principles and adopted to existing tools.

Narayanan et al. proposed the use of Markov chains for password guessing. The method uses conditional probability P (A|B) that character A will follow after character B. The probabilities for all characters A, B are stored in a matrix obtained by the analysis of an existing password dictionary [START_REF] Narayanan | Fast dictionary attacks on passwords using timespace tradeoff[END_REF]. The technique was utilized in Hashcat tool which uses Markov chains for brute-force attacks by default. The probability matrix can be generated automatically using Hcstatgen5 utility and is stored in a .hcstat file. Recent versions of Hashcat use LZMA compression which is indicated by .hcstat2 file extension.

Weir et al. introduced password cracking using probabilistic context-free grammars (PCFG) [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF]. The mathematical model is based on classic context-free grammars [START_REF] Ginsburg | The Mathematical Theory of Context Free Languages[END_REF] with the only difference that each rewriting rule is assigned a probability value. The grammar is created by training on an existing password dictionary. Each password is divided into continuous fragments of letters (L), digits (D), and special characters (S). For fragment of length n, a rewriting rule of the following form is created: T n → f : p, where T is a type of the character group (L, D, S), f is the fragment itself, and p is the probability obtained by dividing the number of occurrences of the fragment by the number of all fragments of the same type and length. In addition, we add rules that rewrite the starting symbol (S) to base structures which are non-terminal sentential forms describing the structure of the password [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF]. For example, password "p@per73" is described by base structure L 1 S 1 L 3 D 2 since it consist from a single letter followed by a single special character, three letters, and two digits. Table 1 shows rewriting rules of a PCFG generated by training on two passwords: "pass!word" and "love@love". There is only one rule that rewrites S since both passwords are described by the same base structure. By using PCFG on MySpace dataset (split to training and testing part), Weir et The proposed approach, however, does not distinguish between lowercase and uppercase letters. Weir extended the original generator by adding capitalization rules like "UULL" or "ULLL" where "U" means uppercase and "L" lowercase. The rules are applied to all letter fragments which increases the number of generated guesses [START_REF] Weir | Using probabilistic techniques to aid in password cracking attacks[END_REF]. After adding capitalization, the notation for letter nonterminals were changed from L n to A n (as alphabetical) since L now stands for lowercase.

While the previous techniques consider only the syntax of passwords, Veras et al. designed a semantics-based approach which divides password fragments into categories by semantic topics like names, numbers, love, sports, etc. With JtR in stdin mode feeded by a semantic-based password generator, Veras achieved better success rates than using Weir's approach or the default JtR wordlist [START_REF] Veras | On semantic patterns of passwords and their security impact[END_REF].

Ma et al. showed how normalization and smoothing can increase the success rate of Markov models. By training and testing on a huge number of datasets, Ma showed that the improved Markov-based guessing could bring better results than PCFGs [START_REF] Ma | A study of probabilistic password models[END_REF].

Weir's PCFG-based technique encountered extensions as well. Houshmand et al. introduced keyboard patterns represented by additional rewriting rules that helped improve the success rate by up to 22%, proposed the use of Laplace probability smoothing, and created guidelines for choosing appropriate attack dictionaries [START_REF] Houshmand | Next gen pcfg password cracking[END_REF]. After that, Houshmand also introduced targeted grammars that utilize information about a user who created the password [START_REF] Houshmand | Using personal information in targeted grammarbased probabilistic password attacks[END_REF].

The current version of Weir's PCFG Cracker consists of two separate tools: PCFG Trainer and PCFG Manager. While PCFG Trainer is used to create a grammar from an existing password dictionary, PCFG Manager generates new password guesses from the grammar -i.e., gradually applies rewriting rules to the starting symbol and derived sentential forms.

At the time of writing this paper, both tools include the support for letter capitalization rules [START_REF] Weir | Using probabilistic techniques to aid in password cracking attacks[END_REF], keyboard patterns [START_REF] Houshmand | Next gen pcfg password cracking[END_REF], as well as the ability to generate new password segments using Markov chains [START_REF] Narayanan | Fast dictionary attacks on passwords using timespace tradeoff[END_REF]. In the training phase, a user can set a coverage value which defines the portion of guesses to be generated using rewriting rules only while the rest is generated using Markov-based bruteforce. A smoothing parameter allows the user to apply probability smoothing as described in [START_REF] Houshmand | Next gen pcfg password cracking[END_REF]. Moreover, the tools contain the support for context-sensitive character sequences like "<3" or "#1" that, if present in the training data, form a separate set of rewriting rules. Such replacements can be used to describe special strings like smileys, arrows, and others.

Despite numerous improvements made by Houshmand [START_REF] Houshmand | Next gen pcfg password cracking[END_REF], users still have to face slow password guessing speed which is currently the bottleneck of the entire process. Besides, the generating of password guesses gets progressively slower as the time goes on and, as we detected, has high memory requirements. Creating a complete wordlist of possible password candidates using PCFGs trained on leaked datasets may take many hours or even days. Moreover, current tools do not provide information about the size of the keyspace, i.e., the number of possible password candidates, and thus the user has no clue about how long will the process take. This obstacle has already been reported as a GitHub issue7 . Weir, however, does not plan to resolve the issue "anytime soon."

Enhancements to PCFG

We focus on making PCFG-based password cracking suitable for practical usei.e., allow the user to create a PCFG, generate a wordlist of password guesses in a short time, and start cracking immediately. To achieve this, we decided to:

-Create a faster "password generator" that could produce more guesses at the same time using the same hardware. -Make a tool to calculate the number of possible password guesses from a PCFG. The number can help estimate the size of an output dictionary as well as the time required to generate all password candidates. -Analyze if modification of an existing grammar can provide any help to the password guessing process. Concretely, if it accelerates the password guessing, or makes it end in a meaningful time.

To verify the success of our efforts, we study the following metrics: a) the number of guesses per time unit, b) the total time of password guessing, c) the number of generated passwords, d) the success rate for testing datasets, i.e., how many newly-generated passwords are present in existing password dictionaries.

Key observations

By analyzing the behavior of Weir's Python PCFG Cracker on various leaked datasets, we observed the following:

-The Python implementation of PCFG Manager uses a priority queue and three processes: one that fills the queue with pre-terminal structures [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF], one that creates terminal structures (password guesses), and one for storage backup. No other parallelization is supported. Thus, the processor cores are not utilized well.

-Processing long base structures like

A 1 D 1 A 2 D 2 A 3 D 3 A 4 D 4 A 5 D 5 is compu-
tationally complex and wastes a lot of time even if their probabilities are insignificant. -Rewriting rules for alpha characters (A), digits (D), and other symbols (O) have all similar probability, while rewriting rules for base structures differ more between each other. -For capitalization of letter fragments, a grammar usually contains few (1 to 4) rules with higher probabilities while the rest have probability below 0.1 and only little impact on success rate.

Long base structures

For every PCFG, possible sentential forms create a tree structure where the starting symbol represents the root node, and terminal structures are leaves. Every edge stands for the application of a rewriting rule that transforms a parent node to a child node. In terms of probabilistic password cracking, terminal structures are password candidates, and base structures (e.g., A 4 D 2 O 1 ) are located on the second level of the tree.

In PCFG Manager, every base structure is processed by Deadbeat dad algorithm [START_REF] Weir | Using probabilistic techniques to aid in password cracking attacks[END_REF]. The goal of this algorithm is to create new children from the current node and ensure that these child nodes are inserted into the priority queue in the correct order. Deadbeat dad replaced the original Next function [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF] and significantly reduced the size of the priority queue at the expense of computing operations [START_REF] Weir | Using probabilistic techniques to aid in password cracking attacks[END_REF].

We analyzed the algorithm and observed that the most expensive task is to find every possible parent of every node which is being inserted into the priority queue. In Weir's PCFG Manager, the task is resolved by a function called dd is my parent that runs in iterations whose count is potentially increased by every non-terminal present in the processed base structure. The deciding factor is the number of different probabilities assigned to the rewriting rules applicable to the non-terminal. If all usable rules have the same probability value, the number of iterations is not increased. The more different probabilities are present, the more rapidly the iteration count grows, if the non-terminal is added to the base structure.

Table 2 shows the number of dd is my parent iterations under different settings. For D 3 non-terminal, all rules have the same probability, and thus D 3 has no impact on the iteration count. For A 1 , rewriting rules have 26 to 29 different probability values (A p 1 ). As a capitalization rule for A 1 , only "L" is used. One can see, the number of iterations grows almost exponentially each time A 1 is added to the base structure.

In PCFGs trained on leaked password datasets, the variedness between rule probabilities is usually high, especially for shorter character fragments. For long base structures, the dd is my parent function may iterate millions of times which significantly slows the password guessing process. Such structures usually have low probability values since they are in most cases created from randomly generated strings, not created by users. We assume, removing such structures

Calculating the number of password candidates

The calculation of possible password guesses from a PCFG is a currently missing 7 feature that is, however, essential for tools presented in this paper. Let size(N ) be the number of terminal structures that can be created by applying rewriting rules on non-terminal N . For base structure B = N 1 N 2 . . . N n , the number of possible password candidates can be calculated as:

cnt base(B) = n i=1 size(N n ). ( 1
)
For grammar G, the total number of possible password candidates is the sum of cnt base(B) for all base structures B ∈ G:

cnt total(G) = B∈G cnt base(B). (2)
The file and directory structure of Weir's PCFG considers a single rewriting rule per line. All rewriting rules have non-zero probability, and thus, all are used. Therefore, size(N ) for non-terminal N = T n (see Section 2) is, in most cases, the number of lines in n.txt file located in a directory for fragments of type T . For example, size(D 3 ) equals the number of lines in Digits/3.txt file. Since letter capitalization rules have been introduced, it is necessary to take them into consideration. Thus, size(A n ) is the number of lines in Alpha/n.txt file multiplied by the number of lines in Capitalization/n.txt file. The calculation shown above is usable for classical PCFG-based approach only, i.e., with the --coverage parameter of PCFG Trainer set to 1. Otherwise, Weir's PCFG Manager would create additional character fragments using bruteforce and Markov chains which is out of the scope of this paper.

The new PCFG Manager

To improve the use of resources, we created an alternative8 to Weir's PCFG Manager. We started with a simple transcription of Python sources to Go programming language that we chose because of its speed, simplicity, and compilation to machine language. Early experiments showed that our Go-based alternative using the same algorithms was about four times faster than the original solution. However, there was still enough space for optimization.

Within all steps performed by the PCFG Manager, generating password guesses from pre-terminal structures [START_REF] Weir | Using probabilistic techniques to aid in password cracking attacks[END_REF][START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF] was the most computationally complex part. Since there is no mutual dependence between the pre-terminals, we decided to modify the program and parallelize this part of the process. Our new design uses a single goroutine (a lightweight thread) for filling the priority queue [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF] with pre-terminal structures, and one to n goroutines for generating terminals in parallel. The n can be set by a user to reflect the processor's capabilities. Moreover, we added a parameter which allows the user to limit the number of generated password guesses. We illustrate both approaches by simplified schematics that display goroutines and data transfer operations. While Figure 1a shows the original design of Weir's PCFG Manager, the parallel version is depicted in Figure 1b.

For synchronization and mutual communication, goroutines use a mechanism called channels that act as FIFO queues. A goroutine can send values to a channel or receive values from it. By default, channels are not buffered and both send and receive operations are blocking. In our solution, we use a buffered channel of size n where the sender is blocked only if the channel contains n values in the queue. Each value represents a pre-terminal structure. The main goroutine (M) implements the Deadbeat dad algorithm [START_REF] Weir | Using probabilistic techniques to aid in password cracking attacks[END_REF] filling the priority queue with preterminals. Every time a pre-terminal is created, it is sent to the buffered channel if there is enough space. Every time the channel is full, the main goroutine is suspended automatically by the send operation. There is no need to generate more pre-terminals at the time they cannot be processed. In contrast to the original version, the proposed design allows to process multiple pre-terminals and generate passwords in parallel if n > 1. In that case, the only apparent drawback is the possible slight change of the password order at the output. This behavior could be resolved by adding a supplementary synchronization mechanism at the output, however, at the cost of performance loss. For practical use, we do not consider this as a large obstacle since for millions of password, the changes are insignificant because the order of larger password blocks is preserved. Moreover, if the user does not set the guess limit explicitly, or if the limit is set in the PCFG Mower (see Section 3.5) instead of PCFG Manager, the output dictionary contains the same passwords, and the success rate would be intact.

By profiling, we later detected that even though we accelerated generating terminal structures, the new bottleneck was at the output, where simple I/O text operations slowed down the entire process. We overcame this obstacle by adding extra output buffers to goroutines that generate terminal structures. The buffers store the terminal structures and are flushed to output after the entire pre-terminal is processed. The final design is illustrated in Figure 1c and the experimental results in Section 4.

Grammar filtering

To increase speed even more, we experimented with various modifications of already-trained grammars. We noticed that removing rules which rewrite the starting symbol into long base structures brings a significant speedup without higher impact on a success rate. The motivation for such filtering was discussed in Section 3.2. We automated the process by creating a simple script that automatically filters out all base structures longer than a user-defined maximum. At this point, we were able to generate much more passwords per time unit. However, without a manually-defined limit for password guesses, the total amount of time required for generating was still extensive. From a practical perspective, any limit to guess count means that there is always a part of the grammar that is never used and unnecessarily wastes memory during the guess generation. Such consideration led us to speculate about reducing the size of the grammar instead of limiting guesses in PCFG Manager.

We came with an idea to remove the least significant rewriting rules from the grammar. We are aware of the fact that any removal of rules from alreadycreated PCFG without adjusting probability values results in a mathematically incorrect grammar where the total probability of rules that rewrite some nonterminals may be lower than one. For practical use with the PCFG Manager, it does not matter. The goal of the filtering is to make the output dictionary more compact and to ensure that generating passwords will end in a meaningful time. Besides, having a reduced grammar that can be processed entirely, ensures that even the parallel run of PCFG Manager generates the same passwords every time. Nevertheless, the strongest motivation for grammar filtering is a potentially massive saving of processor time. Putting a limit before the guessing even starts prevents the Deadbeat dad algorithm from performing many useless derivation steps on trees that never form terminal passwords due to a low probability.

As denoted above, rules for alpha characters, digits, and special symbols usually have similar probabilities, thus removing them leads to a considerable loss of information which decreases the success rate. Rulesets for base structures and capitalization, on the other hand, contain many insignificant rewriting rules that can be removed safely. We created a tool called PCFG Mower9 which can:

-Calculate the total number of possible password guesses from a PCFG and inform the user about achievable keyspace. Moreover, if the user knows an average speed of password guessing, it is possible to estimate the total time required for generating all password candidates. -Filter a PCFG by performing an automatic removal of rewriting rules based on a set of options entered by the user.

To verify our assumptions, we created a simple PCFG reduction algorithm that is implemented in PCFG Mower and shown in Figure 2. The goal of the algorithm is not to provide a universal solution, but to validate or disprove that systematic PCFG filtering brings a possible benefit to password cracking. Besides the Input: original grammar, limit, bs, cs Output: reduced grammar 1: reduce = true, i = 0 2: repeat 3: i++ 4: count = password count() 5:

if count ≤ limit then 6: reduce = false 7:

end if 8:

if reduce then 9:

Remove as many base structures as required to reduce their total probability by bs.

10:

Remove all capitalization rules that have probability lower than i × cs.

11:

end if 12: until not reduce Fig. 2: PCFG reduction algorithm original grammar, it takes the following input parameters: limit defining the maximum number of password guesses to be generated, and probability values b s , c s . While b s allows to set how rapidly should the algorithm remove base structures, c s sets the same for capitalization rules. The output of the algorithm represents a PCFG which generates the maximum of limit password guesses.

Experimental results

In this section, we demonstrate the practical benefits of our enhancements to PCFGs. For experimental purposes, we work with both original and modified datasets from real password leaks. As data sources, we used SkullSecurity 2 pages and SecLists 3 repository. All employed datasets are enlisted in table 3. For shorter notation, we assign each a unique identifier (ID). The last row (def) represents the default PCFG from Weir's PCFG Cracker 1 , which is said to be trained on a random sample of million passwords from RockYou dataset.

The table shows the number of passwords in the dataset (pw count), its size, and the average password length (avg). The other columns illustrate how a PCFG trained on the dataset looks like. We show the number of rewriting rules for alpha characters (A), digits (D), other characters (O) as well as the number of rewriting rules for base structures (base) and capitalization (cap).

The performance of PCFG Manager

At first, we measured the acceleration that can be achieved using our new PCFG Manager in contrast with the original one from Weir et al. [START_REF] Weir | Password cracking using probabilistic context-free grammars[END_REF]. Table 4 shows experimental results of generating password guesses using PCFG trained on Darkweb2017-10000 dataset (dw), RockYou-75 dataset (ru75), and the default PCFG (def) used in Weir's cracker. All three experiments were performed using We also decided to study the influence of disk I/O speed, so that we measured everything using HDD and then using SSD. In all cases, we measured how many password guesses we can generate within 3 minutes.

Our solution was from 8 to 40 times faster than the original one. Using Darkweb dataset (see Figure 3) resulted in lowest acceleration since it contains long and complex base structures. With the default PCFG (see Figure 4) and Rockyou-75 dataset (see Figure 5), we were able to generate much more password guesses, and the difference between HDD and SSD is more noticeable.

The impact of PCFG filtering

The second set of experiments aim to examine the effects of our attempts to reduce the grammar. Table 5 shows the results of training, modification, generating password guesses, and checking success rate using multiple datasets.

The experiments were performed using Intel(R) Core(TM) i7-7700K CPU with 32 GB RAM and an SSD. Since generating password guesses using non-modified PCFGs would take hours and days, we set a time limit of 10 minutes to all measurements -every time the PCFG manager exceeded the 10-minute interval, it was stopped.

The first column (tr) shows which dataset we used for training to create the PCFG. For all training datasets, the first line represents generating password guesses using the original grammar -i.e., without any modification. The longbase modification stands for the grammar where we removed base structures longer than 10 characters (5 non-terminals). In other measurements, we used a grammar with already-removed long base structures and reduced it using PCFG Mower described in Section 3. The mow-n modification means that we performed longbase first and then we set the limit of the PCFG reduction algorithm to n passwords. We experimented with the following limit values: 1,000,000,000 (1000M), 500,000,000 (500M), and 20,000,000 (20M) passwords. In all cases, the b s and c s constants were set to 0.001 to achieve fine-grained filtering. Since the algorithm removes selected rules, we illustrate the changes done to the grammars in each step. For every modification, we display the preserved number of rewriting rules for base structures (base) and capitalization (cap). Next columns inform about password guessing. We display the amount of time required to generate the output dictionary (time), (or 10m * if we reached the time 10-minute limit), the size of the output dictionary (out size) and the number of its passwords in millions (mop). The rest displays the success rate of password guessing on testing datasets -i.e., the percentage telling how many generated password guesses were included in different testing datasets. The last column displays the average success rate impact (ASRI) which is calculated as:

ASRI = n i=1 (SR mod i -SR orig i ) n
where SR orig i is the success rate on testing dataset number i before the modification of the PCFG, and SR mod i is the success rate on testing dataset number i after the modification of the PCFG, and n is the total number of testing datasets. In our case, n = 4. We use ASRI to analyze the influence of our modifications. Positive ASRI means that the success rate was improved while negative stands for decrease.

As we can see from results, removing long base structures resulted in a massive increase of password guessing speed which enabled to generate much more passwords within 10 minutes. We achieved the highest acceleration on dw and r65 since they contain very complex passwords that create enormously long base structures. After the modification, we were able to generate over 14 times more password guesses. In contrast, training on ms and tl creates more simple grammars, and thus the speedup was not as rapid. Removing long base structures showed almost no impact on the success rate which confirms our assumption that their importance is negligible. From 16 testings, only 8 led to decrease by a maximum of 0.06 %. To our surprise, the ASRI was mostly positive since in 6 cases, removing long base structures improved the success rate by up to 0.7 % thanks to more passwords generated within the same time.

Next measurements analyzed grammars filtered by PCFG Mower to verify if the removal of low-probability rewriting rules brings any benefit. In all cases, the mow modification allowed the PCFG Manager to process the entire grammar in less than 4 minutes, showing that it can provide a suitable alternative to a "hard" limit for password guessing. More compact PCFGs produced smaller dictionaries. With more compact PCFGs, the generated dictionaries were smaller as well. Again, we achieved the best results with dw and r65 datasets, where we were able to reduce the size from 12 GB (longbase) to 112 MB dictionary, and from 25 GB to 130 MB with a loss of success rate below 4 % in all cases. For ms and tl, filtering the grammar spared time and space as well, however, the mow-20M limit was too strict to provide satisfactory results. For dw, we received the same results with mow-1000M and mow-500M. The dw -trained grammar contains a high number of base structures with similar probabilities. Thus, a lot of them was removed by mow-1000M modification, and no further filtering was necessary.

Evaluation

By modification of both PCFG Manager and existing grammars, we were able to make password guessing many times faster. What most helped the speedup was the use of a compiled programming language, the parallelization of generating terminal structures and removing rewriting rules for long base structures. For datasets we analyzed, such rules caused "more harm than good." The rewriting rules for long base structures mostly had insignificant probabilities but compli-cated the calculation of the computationally-complex Deadbeat dad algorithm. In all cases, the removal accelerated the password guessing dramatically.

Filtering grammars with PCFG Mower reduced the time required for password guessing rapidly. The settings, however, have to be selected wisely. With our experimental setup, we achieved the best results with PCFG Mower limit set to 500 millions of passwords. Stricter limitation produced decent results for only some cases. We assume that the success rate highly depends on the nature of selected datasets, and thus there is no universal solution.

Conclusion

Probabilistic methods certainly have their place in the area of password cracking. While Markov chains were adopted to existing tools a long time ago, probabilistic context-free grammars are currently more a subject of academic research than a ready-to-use technique. However, as the development of cracking methods continues by researchers, communities, and commercial subjects, the situation may change. Even the authors of Hashcat consider10 adding support for generating "slow candidates."

From our standpoint, one of the main factors that currently complicate the use of PCFG-based techniques is the extensive amount of time required to generate password guesses. By using both analytic and experimental approach, we identified the critical spots that slowed down the entire process. We proposed methods that optimize the password guessing and allow better use of hardware resources. We experimentally proved that our new PCFG Manager is capable of generating passwords 8 to 40 times faster than the original tool from Weir et al.

Moreover, we proposed a way of PCFG filtering which provides a resourcesaving alternative to a "hard" password guess limit. We showed that the systematic removal of selected rewriting rules might reduce the total amount of time required to generate password candidates without having a significant impact on the success rate. If one decides to use the filtering techniques, we recommend starting with the removal of long base structures that produce the leastprobable passwords and perceptibly increase the number of necessary processor operations.

In our future research, we want to perform a more detailed analysis of the relation between PCFG filtering and the success ratio which may discover new factors that have not been revealed yet. Since the practical use of password cracking often involves a distributed environment, we currently work on distributed PCFG-based password guessing techniques which may provide a smarter alternative for a classic dictionary attack. and "ICT tools, methods and technologies for smart cities" project, no. FIT-S-17-3964 granted by Brno University of Technology. The work is also supported by Ministry of Education, Youth and Sports of the Czech Republic from the National Programme of Sustainability (NPU II) project "IT4Innovations excellence in science" LQ1602.

Fig. 1 :

 1 Fig. 1: The architecture of PCFG Manager in Python and Go (PT -pre-terminal structure, T -terminal)

Fig. 3 :Fig. 4 :

 34 Fig. 3: No. of guesses within 3 minutes using Darkweb-trained PCFG

Fig. 5 :

 5 Fig. 5: No. of guesses within 3 minutes using Rockyou-75-trained PCFG

Table 1 :

 1 An example of PCFG rewriting rules

	al. were able to crack 28% to 128% more passwords
	in comparison with the default ruleset from John the Ripper (JtR) tool 6 using
	the same number of guesses.

Table 2 :

 2 The number of iterations of dd is my parent function from the grammar speeds up password generation several times and does not noticeably decrease success rate at cracking sessions.

Table 3 :

 3 Password datasets used for experiments a computer with Intel(R) Core(TM) i7-4700HQ CPU with 8 GB RAM.

		dataset		PCFG
	ID	name	pw count size avg	A	D	O base cap
	dw Darkweb2017-10000.txt 10,000 82.6 kB 7	5,244	947 30 323 83
	r65	rockyou-65.txt	30,290 344.5 kB 7 17,845 4,213 35 256 39
	r75	rockyou-75.txt	59,187 478.9 kB 7 30,670 10,601 51 351 51
	ms	myspace.txt	37,126 354.2 kB 8 22,587 4,273 133 1,574 179
	tl	tuscl.txt	38,820 324.7 kB 7 26,806 6,518 71 1,290 242
	pr probab-v2-top12000.txt 12,645 100.2 kB 6 11,117 534	1 125 23
	def Random million passwords from RockYou	330,343 145,510 906 84,307 950

Table 4 :

 4 No. of guesses and acceleration of PCFG manager

	training manager	HDD	SSD
		Python	3,022,923 2,948,532
	dw	Go	24,592,908 24,609,579
		acceleration	8.14 x	8.35 x
		Python	29,613,726 32,402,490
	def	Go	405,819,926 485,244,534
		acceleration	13.70 x	14.98 x
		Python	18,418,684 20,843,491
	r75	Go	490,635,443 842,695,475
		acceleration	26.64 x	40.43 x

Table 5 :

 5 Success rates of original and modified PCFGs (* -reached the time limit)

https://hashcat.net/wiki/doku.php?id=hashcat_utils#hcstatgen

https://www.openwall.com/john/

https://github.com/lakiw/pcfg_cracker/issues/9

https://github.com/Dasio/pcfg-manager

https://github.com/findo11/pcfg_mower

https://hashcat.net/forum/thread-7903.html

Acknowledgements The research presented in this paper is supported by "Integrated platform for analysis of digital data from security incidents" project, no. VI20172020062 granted by Ministry of the Interior of the Czech Republic

://github.com/lakiw/pcfg_cracker 2 https://wiki.skullsecurity.org/index.php?title=Passwords 3 https://github.com/danielmiessler/SecLists/tree/master/Passwords 4 https://golang.org/