Zhoulai Fu

Modularly Combining Numeric Abstract Domains with Points-to Analysis, and a Scalable Static Numeric Analyzer for Java

This paper contributes to a new abstract domain that combines static numeric analysis and points-to analysis. One particularity of this abstract domain lies in its high degree of modularity, in the sense that the domain is constructed by reusing its combined components as black-boxes. This modularity dramatically eases the proof of its soundness and renders its algorithm intuitive. We have prototyped the abstract domain for analyzing real-world Java programs. Our experimental results show a tangible precision enhancement compared to what is possible by traditional static numeric analysis, and this at a cost that is comparable to the cost of running the numeric and pointer analyses separately.

Introduction

Static numeric analysis -that approximates values of scalar variables and their relationship -has drawn on a rich body of techniques including abstract domains of intervals [START_REF] Cousot | Static determination of dynamic properties of programs[END_REF], polyhedron [START_REF] Cousot | Automatic discovery of linear restraints among variables of a program[END_REF] and octagons [START_REF] Miné | The octagon abstract domain[END_REF] etc. which have found their way into mature implementations. In a similar way, the analysis of properties describing the shape of data structures in the heap has flourished into a rich set of pointsto and alias analyses which also have provided a range of production-quality analyzers. However, when extending numeric analyses to heap-manipulating programs we are immediately faced with the issues that pointers introduce aliases which make program reasoning difficult because understanding the communication between numeric properties and dynamic data structures is needed. This gives rise to the problem of combining static numeric analysis and heap analysis.

The combination of the two analyses has been studied, but the solutions proposed so far tend to be complex to implement or impractical to analyze large programs. For example, Simon [START_REF] Simon | Value-Range Analysis of C Programs[END_REF] shows how to combine ad hoc numeric abstract domains with manually refined flow-sensitive points-to analyses. His combination approach requires extensive experiences and intimate familiarity with the abstract domains themselves, thereby hard to implement. Miné's abstraction [START_REF] Miné | Field-sensitive value analysis of embedded c programs with union types and pointer arithmetics[END_REF], by contrast, is designed to be modular. The purpose was to lift existing abstract domains in ASTREE [START_REF] Bertrane | Static analysis by abstract interpretation of embedded critical software[END_REF] developed with several man-years to cope with pointer-aware programs. Reusing existing components as modules is particularly important in that context. However, Miné's framework is based on type-based pointer analysis, which is cheap but too coarse by its nature. This prohibits the general practicability of the Miné's analysis. At the other extreme, shape-analysis [START_REF] Sagiv | Parametric shape analysis via 3-valued logic[END_REF] based approaches come with sophisticated pointer analyses and can indeed infer non-trivial properties. However, analyses that are based on shape abstraction can hardly (see [START_REF] Calcagno | Compositional shape analysis by means of bi-abduction[END_REF][START_REF] Yang | Scalable shape analysis for systems code[END_REF] for exceptions) run on large programs.

Different from the work mentioned above, our objective is to develop a combined analysis satisfying the following requirements:

-Modular design: The combined analysis should enable the reusing of existing analyses that have been developed since decades. The construction of the combined analysis should only depend on the interfaces, not the specific implementations, of its components. -Scalability: We are seeking a tool that runs on codes of hundreds of thousands of lines. We examine the feasibility of our analysis over moderate and large sized benchmarks, and ensure that the combined analysis only presents small complexity overhead compared with its component analyses. -Precision: Although the query of scalability inevitably demands a sacrifice on precision, we inspect that the combined analysis has to be, at least, as precise as its components.

The core contribution of this work is a theoretical foundation that combines in a generic manner an abstract domain dedicated to static numeric analysis of programs without allocations, and an abstract domain for points-to static analysis.

On the practical side, we have implemented the abstract domain, using the Java Optimization Framework SOOT [START_REF] Vallée-Rai | Soot -a java bytecode optimization framework[END_REF] as the front-end, and relying on the abstract domains from existing static analysis libraries such as the Parma Polyhedra Library PPL [START_REF] Bagnara | The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems[END_REF] and the SOOT Pointer Analysis Research Kit SPARK [START_REF] Lhoták | Scaling Java points-to analysis using Spark[END_REF]. This prototype analyzer, called NumP, has been run on all 11 programs in the Dacapo-2006-MR2 [START_REF] Blackburn | The DaCapo benchmarks: Java benchmarking development and analysis[END_REF] benchmark suite. The suite is composed of moderate and large sized program with rich object behaviors and demanding memory system requirements. Our experiments confirm that the combined analysis is feasible even for large-sized programs and that it discovers significantly more program properties than what is possible by pure numeric analysis, and this at a cost that is comparable to the cost of running the numeric and pointer analysis separately.

Organization of the paper

The interfaces of traditional numeric and pointer analyses are specified in Sect. 2. The intuition of our analysis is illustrated with a small example in Sect. 3. In Sect. 4, we define the modeled language and its concrete semantics. The abstract domain and its operators are presented in Sect. 5. Experimental results are shown in Sect. 6. Finally, we compare our analysis with related work and conclude in Sect. 7 and 8.

The formal underpinning and semantic correctness of the combination technique are presented in the author's Ph.D. thesis [START_REF] Fu | Static Analysis of Numerical Properties in the Presence of Pointers[END_REF].

Analysis Interfaces

This section is define the interfaces of two existing analysis, static numeric analysis and points-to analysis.

General notation. For a given set U , the notation U ⊥ means the disjoint union U ∪{⊥}. Given a mapping m ∈ A → B ⊥ , we express the fact that m is undefined in a point x by m(x) = ⊥. Syntactical notations. Primary data types include: scalar numbers in I, where I can be integers, rationales or reals; and references (or pointers) in Ref . Primary syntactical entities include the universe of local variables and fields. They are denoted by Var and Fld respectively. An access path is either a variable or a variable followed by a sequence of fields. The universe of access paths is denoted by Path. We subscript Var τ , Field τ , or Path τ with τ ∈ {n, p} to indicate their types as a scalar number or a reference, respectively. The elements in these sets can also be sub-scripted with types. The types will be omitted if they are clear from context.

We use Imp n to refer to the basic statements only involving numeric variables and use the meta-variables s n to range over these statements. Similarly, we let Imp p be the statements that only use pointer variables and let s p range over these statements. Below we list the syntactical entities and meta-variables used to range over them.

k ∈ I scalar numbers r ∈ Ref concrete references x τ , y τ ∈ Var τ numeric/pointer variables f τ , g τ ∈ Field τ numeric/pointer fields u τ , v τ ∈ Path τ numeric/pointer access paths s n ∈ Imp n x n = k | x n = y n | x n = y n z n | x n y n s p ∈ Imp p x p = new | x p = y p .f p | x p = y p | x p .f p = y p
where ∈ {+, -, * , /}, and is an arithmetic comparison operator.

Static numeric analysis

Static numeric analysis can be modeled as an abstract interpretation of Imp n . We use the term numeric property [START_REF] Miné | Weakly Relational Numerical Abstract Domains[END_REF] for any conjunction of formula in a certain theory of arithmetic. For example, the numeric property {x 2 + y 2 ≤ 1, x ≤ 0, y ≤ 0} is composed of the conjunction of three arithmetic formulas As usual, an environment maps variables to their values. We consider numeric environments:

Num Var n → I ⊥ (1)
The relationship between an environment and a property can be formalized by the concept of valuation. We say that n is a valuation of n , denoted by

n |= n (2)
if n becomes a tautology after each of its free variables, if any, has been replaced by its corresponded value in n.

Definition 1 (Interface of the traditional numeric analyzer).

(Imp n , ℘(Num), [|•|] n , γ n , Num , [|•|] n )
The concrete numeric domain and the abstract numeric domain for the language Imp n are ℘(Num) and Num respectively. They are related by the concretization function

γ n : Num → ℘(Num) defined by γ n (n ) = {n ∈ Num | n |= n }.
The partial order is consistent with the monotonicity of γ n , i.e., n 1 n 2 implies γ n (n 1 ) ⊆ γ n (n 2 ). For each statement s n of Imp n , the concrete semantics is given by a standard transfer function

[|s n |] n ∈ ℘(Num) → ℘(Num). The abstract semantics [|•|] n satisfies the soundness condition: [|•|] n • γ n ⊆ γ n • [|•|] n (3)
At last, we assume the availability of a join operator and a widening operator . The join operator is assumed to be sound with regard to the partial order , and the soundness of is specified in [START_REF] Cousot | Abstract interpretation frameworks[END_REF].

Pointer analysis

Pointer analysis can be modeled as an abstract interpretation of Imp p . Let Pter be the set of concrete states in Imp p . Traditionally, a state p ∈ Pter is a pair of environment and heap. We write p to range over them.

p ∈ Pter (Var p → Ref ⊥ ) × ((Ref × Fld p ) → Ref ⊥ ) (4)
The essence of pointer analysis is the process of heap disambiguation, i.e., the analysis partitions Ref into a finite set H and then summarizes the run-time pointer relations via elements h in H. The process is based on the naming scheme.

Definition 2. The naming scheme is a mapping from concrete references to their names in H. The names used by the naming scheme of a pointer analysis are called abstract references or abstract locations.

∈ Ref → H (5)
We say r ∈ Ref is abstracted by h ∈ H if r h. It is required that the memory regions abstracted by different abstract references have no common concrete reference.

∀h 1 , h 2 ∈ H, h 1 = h 2 ⇒ -1 (h 1 ) ∩ -1 (h 2 ) = ∅.
This paper considers points-to analysis [START_REF] Emami | Context-sensitive interprocedural points-to analysis in the presence of function pointers[END_REF] that is widely used in heap analysis. The lattice used in the points-to abstract domain is commonly called pointsto graph. This graph has two kinds of arcs, the unlabeled arcs from a variable to an abstract reference and the labeled arcs between abstract references that are labeled by a field. The abstract domain used in points-to analysis is a set of points-to graphs, denoted by Pter .

Pter (Var p → ℘(H)) × ((H × Fld p ) → ℘(H)) (6)
Remark 1. Points-to analysis is based on a naming scheme that is flow independent. In other words, a given analysis pass of points-to analysis allows for a unique naming scheme, whatever the abstractions of the heap. It is worth noting that this property on the naming scheme is respected by all variants of points-to analysis (including flow-sensitive points-to analysis). In this presentation, we use a typical naming scheme to name heap elements after the program point of the statement that allocates them.

Definition 3 (Interface of traditional points-to analyzer).

(Imp p , ℘(Pter ), [|•|] p , γ p , Pter , [|•|] p )
The concrete domain and the abstract domain of points-to analysis are denoted by ℘(Pter ) and Pter respectively. They are related by a monotone concretization function γ p : Pter → ℘(Pter ). The concrete semantics is interfaced by a standard transfer function

[|•|] p ∈ ℘(Pter ) → ℘(Pter ). The abstract semantics [|•|] p ∈ Pter →
Pter is provided by a static numeric analyzer. This analyzer is assumed sound:

[|•|] p • γ p ⊆ γ p • [|•|] p (7)
3 Combining Points-to and Numeric Analysis: Intuition

This section presents the intuition behind the technique of combining points-to analyses and numeric analyses. The idea is to use the names computed by the points-to analysis to create summarized variables that represent the numeric values stored at particular heap locations.

Example 1. Consider the Java snippet in Listing 1.1. An abstract class Unsigned uses unsigned numbers to represent both positive and negative values. Unsigned has two subclasses Pos and Neg for this purpose. It is the responsibility of clients to ensure the underlined contract, i.e., the objects of type Unsigned must hold non-negative values. The Java source code takes an array buf and passes the elements to the list elem of type List. The list has a field item for data type Unsigned and a field next of type List. The compound condition structure (l. 7-14 in Listing 1.1) creates an object of class Pos or Neg according to whether n is positive or not. In both cases, data.val is assigned to the absolute value of n so that the assumed property of unsignedness can be preserved. From l. 15 to l. 19, the program allocates a new cell to store data and links it to the list created by the precedent iteration.

Below we show how we infer the following properties at the end of the program (l. 21).

-Prop1 Each list element of is in the range of 0 to 9:

∀l ≥ 0, hd.next l .item.val ∈ [0, 9] -Prop2 Each array element of buf is in the range of -9 to 7: buf [ * ] ∈ [-9, 7]
.

1 i n t [ ] buf = { -9 , 7 , 3 , -5 } ; / / h 1 2 Unsigned data = null ; 3 L i s t hd = null ; 4 i n t i d x = 0 ; 5 while ( i d x < buf . l e n g t h ) { 6 i n t n = buf [ i d x ] ; 7 i f ( n > 0 ) { 8 data = new Pos ( ) ; / / h 2 9
data . v a l = n ; Listing 1.1: A Java snippet We start with a flow-insensitive points-to analysis. A single points-to graph for the whole program can be obtained (Fig. 2). Semantically, the points-to graph disambiguates the heap by telling what must not alias. We derive a summarized variable δ h,val for each pair of heap location h and field val. The key point is, numeric values bound to syntactically distinct summarized variables are guaranteed to be stored at different concrete heap locations. In line with the semantics of points-to graph, the analysis of the program in Listing 1.1 can be treated as an extended numeric analysis. This analysis is called "extended" because it not only deals with scalar variables, but also deals with summarized variables. Listing 1.2 illustrates the semantics actions taken by our analysis. From l. 1 to l. 4, the summarized variable δ h1,[ * ] is updated with -9, 7, 3 and -5 successively. Since more than one run-time heap locations of the array buf can be associated with δ h1,[ * ] , the semantics action is a weak update (denoted by . =), i.e., accumulating values rather than overwriting them. The semantics action at l. 7 assigns the summarized variable δ h1,[ * ] to the scalar variable n. Note again that this abstract semantics should be distinguished from the abstract semantics of assignment in traditional numeric domain. This is because we should not establish a numeric relation between δ h1,[ * ] and n as in traditional static numeric analysis. Here we use . = to make a distinction. Intuitively, the assignment of δ h1,[ * ] to n should be abstracted as assigning the possible values of δ h1,[ * ] to n without coupling δ h1,[ * ] and n. The rest of the semantics actions in the listing should be clear now. The assignments to scalar variables at l. 5 and l. 14 are the same as in traditional numeric domains. The assignments at l. 9, 10, 12, 13 are weak update to δ h2,val and δ h3,val since both h 2 and h 3 are pointed to by the variable data following the points-to graph.

1 δ h 1 ,[ * ] . = -9 ; 2 δ h 1 ,[ * ] . = 7 ; 3 δ h 1 ,[ * ] . = 3 ; 4 δ h 1 ,[ * ] . = -5 ; 5 i d x = 0 ; 6 while ( ? ) { 7 n . = δ h 1 ,[ * ] ; 8 i f ( n > 0 ) 9 δ h 2 ,val . = n ;

Variable names buf

data # # elem ' ' hd Allocation sites h1 h2 h3 h4 next k k item q q item j j
By performing the extended interval analysis, we are able to infer these invariants at the end of the program: δ h2,val ∈ [0, 9]∧δ h3,val ∈ [0, 9] and δ h1,[ * ] ∈ [-9, 7], which imply Prop1 and Prop2 respectively. Remark 2. The compelling part of this approach should not be the semantics actions presented so far, but the way that they can be constructed by an interplay between traditional numeric domains and points-to analysis. The advantage of this approach is that this interplay does not requires knowledge beyond the interfaces of the components in question. As demonstrated by our implementation of the analysis and its experimental results, this approach allows for direct access to many existing abstract domains including their join, widening and narrowing operators which are known difficult to implement. This paper focuses on how to deal with language Imp np . The statements in Imp np include those in Imp n and Imp p , and two more statements in the forms of y p .f n = x n and x n = y p .f n . We write s np to range over Imp np .

s np ::= s n | s p | y p .f n = x n | x n = y p .f n (8)
A concrete state in Imp np can be regarded as a pair of an environment and a heap

State = Env (Var n → I ⊥ ) × (Var p → Ref ⊥ ) × ((Ref × Fld n ) → I ⊥ ) × ((Ref × Fld p ) → Ref ⊥ ) Heap (9)
We can turn this domain into an isomorphic shape

State Num[(Ref × Fld n ) ∪ Var n ] × Pter ( 10
)
where

Num[(Ref × Fld n ) ∪ Var n ] extends Num to (Ref × Fld n ) ∪ Var n ) → I ⊥ .
Remark 3. The isomorphism consists of a crucial step. It prepares the re-use of the abstract pointer values when extending the numeric domains to cover properties about heap values.

Regarding states as [START_REF] Cousot | Abstract interpretation frameworks[END_REF] allows us to express the concrete semantics of Imp np via those of Imp n and Imp p . As a shortcut, we set We use the lifting of -→ to the powerset ℘(State). as the collecting semantics of Imp np , denoted as

D = Ref × Fld n (11
[|•|] λs : Imp np .post[-→ (s)] (12)
n = {δ h2,val ∈ [0, 9], δ h3,val ∈ [0, 9], δ h1,[ * ] ∈ [-9, 7]} ( 15
)
and p is the points-to graph specified in Fig. 2

→ H to Ref × Fld n → H × Fld n .
We define the space of instantiation as a set of mappings from ∆ to D.

Ins {σ : ∆ → D | σ(h, f n ) = (r, g n ) ⇒ h = (r) ∧ f n = g n } (16)
Definition 7. The concretization function γ np of NumP → ℘(State) is defined as

γ np (n , p ) {(n, p) | p ∈ γ p (p ) ∧ ∀σ ∈ Ins : n ∈ γ n • [σ](n )} ( 17
)
where we denote by [σ] the capture-avoiding substitution operator that replaces all the free occurrences of δ in n ∈ Num [∆ ∪ Var n ] with σ(δ).

Example 2. Consider the following program: The transfer function for updating (n , p ) with s n can be defined as:

1 L i s t hd = null , tmp ; 2 i n t i ; 3 f o r ( i = -1 7 ; i < 4
[|s n |] (n , p ) [|s n |] n n , p (19)
If s n is an assertion in Imp n , p may be refined. For example, consider the compound statement1 if (a > 0) p = q where p and q are reference variables and a is a numeric variable. Although it should be possible to perform a deadcode elimination using inferred numeric relations, similar to Pioli's conditional constant propagation [START_REF] Pioli | Combining interprocedural pointer analysis and conditional constant propagation[END_REF], we still use the Eq. ( 19) for the ease of implementation.

Transfer function for s p It is also sound to assume that s p has no effect upon n . Yet the reasoning is different from the above case. For example, if (n , p ) is the state shown on Eq. ( 18), how can we tell whether an assignment of pointers operation modifies n or not? Recall that the intended semantics of δ h,val → [START_REF] Fu | Static Analysis of Numerical Properties in the Presence of Pointers[END_REF]41] is that every value stored in each (r, val) satisfying (r) = h must be in the range of [-17, 41]. That is to say, n represents a fact about the numeric content stored in the corresponding concrete references. Since a pointer assignment can by no means modify any numeric values stored in the heap, the algorithm to update (n , p ) with s p can be written as:

[|s p |] (n , p ) n , [|s p |] p p (20)
Transfer function of y p .f n = x n Consider an assignment y p .f n = x n with y p pointing to h ∈ H. We regard y p .f n = x n as an weak update to summarized variable δ h,fn , That is, the field f n of one of the concrete objects represented by h is to be updated with the value of x n , while the other concrete objects represented by h remain unchanged. This effect can be approximated by λn .n

[|δ h,fn = x n |] n (n ). Below, we write p y p .f n ⇓ δ (21)
if δ is associated with (h, val) and y p points to h. The transfer function of y p .f n = x n can be modeled by joining the effects of weak update of all δ by x n such that p y p .f n ⇓ δ.

[|y p .f n = x n |] (n , p )     p yp.fn⇓δ n [|δ = x n |] n (n )   , p   (22)
Note that it is not necessary to compute transfer functions for assertions involving field expressions for they are transformed beforehand by our front-end SOOT to assertions in Imp n or in Imp p . For instance, a source code if (x.f > 0) ..., is transformed to a = x.f; if (a > 0) ... before our analysis. This issue was carefully studied and solved by Gopan et al. [START_REF] Gopan | Numeric domains with summarized dimensions[END_REF]. The authors showed that it would be wrong to correlate a summarized dimension δ to a nonsummarized dimension x n even if the former is assigned to the later; they argued that the correct way to assign a summarized dimension δ to a non-summarized dimension x n takes three steps: first, copy the summarized dimension δ to a fresh δ , and then relate x n with δ using traditional abstract semantics for assignment. Finally, the newly introduced dimension δ has to be removed. Intuitively, the resulting abstract value keeps the possible (abstract) values of δ without being correlated with it. Gopan et al. have introduced four non-standard operators, in particular, "drop" that removes dimensions, and "expand" that copies dimensions. We use

Transfer function of x

[|x n = y p .f n |] (n , p ) p yp.fn⇓δ G(x n , δ) n , p (23)
where Gopan's operator G(x n , δ) is the composition of the three steps described above:

G(x n , δ) λn . drop δ • [|x n = δ |] n • expand δ,δ n (24)
Above, we assume dimension δ does not belong to the dimensions of n in question.

Example 3. Let n = δ → [0, 1]
. Even if we use a relational domain like polyhedral analysis, only G(x, δ)n = x → [0, 1], δ → [0, 1] can be obtained, while traditional numeric domains would establish a relationship between x and δ. 20), ( 22) and ( 23 Proof. For all n ∈ Num [∆ ∪ Var n ] and p ∈ Pter , we prove

Theorem 1 (Soundness). The transfer functions [|•|] :

Imp np → (NumP → NumP ), defined in (19), (
[|x p .f n = y n |] (γ np (n , p )) ⊆ γ np ([|x p .f n = y n |] (n , p )) (25)
By the definitions of [|x p .f n = y n |] and [|x p .f n = y n |] and the monotony of γ δ , it is sufficient to show for any d such that γ p (p ) x p .f n ⇓ d, we have

[|d = y n |] n • γ δ (n ) ⊆ γ δ (n [|δ = y n |] n (n )) (26)
where we note δ = (d).

By the definition of γ δ , it is then sufficient to prove a stronger condition:

∀σ ∈ Ins : [|d = y n |] n • γ n • [σ](n ) ⊆ γ n • [σ](n ) ∪ γ n • [σ]([|δ = y n |] n (n )) ( 27
)
Given an instantiation σ (as defined in Eq. ( 6)), we make two cases to conclude:

-Case I: σ does not map δ to d. By consequence d does not appear in [σ](n )

and

[|d = y n |] n • γ n • [σ](n ) = γ n • [σ](n ).
This concludes this case. -Case II: σ maps δ to d. We can then simplify the right part of ( 27) because

[σ]([|δ = y n |] n (n )) = ([|d = y n |] n • [σ](n )).
We then conclude this last case using the soundness of [|d = y n |] n .

Join and widening

The join of two facts is defined as the set of all facts that are implied independently by both. Thanks to our hypothesis of flow independent naming scheme (in Sect. 2.2), the join and widening of NumP are easy to define: we just have to compute the join (or widening) component wise. Then, if a concrete state (n, p) is in γ np (n 1 , p 1 ) or γ np (n 2 , p 2 ), it is also in the concretization of (n

1 n 2 , p 1 ∪ p 2 ).
Thus the join of (n 1 , p 1 ) and (n 2 , p 2 ) is the join of n 1 and n 2 , paired with the join of p 1 and p 2 (Sect. 2). The case for widening is similar.

(n 1 , p 1 ) (n 2 , p 2 ) = (n 1 n 2 , p 1 ∪ p 2 ) (28)
(n 1 , p 1 ) (n 2 , p 2 ) = (n 1 n 2 , p 1 ∪ p 2 ) (29)

Constraint system with a flow-insensitive points-to analysis

In our implementation, we use a flow-insensitive points-to analysis as a preanalysis step. It is worth nothing that using flow-insensitive variant does not cause any soundness issue. This is because the soundness of our analysis is based on the soundness of its component numeric domains and pointer analysis; taking the flow-insensitive points-to graph during all propagation can be modeled as an analysis that is initialized with a set that is larger than the least fix point of a flow-sensitive analysis, and propagates in the style of skip, which satisfies the soundness requirement for the pointer analysis component. Let F (s) λn .fst • [|s|] (n , p f i ), where p f i is the flow-insensitive pointsto graph, and fst is the operator that extracts the first element from a pair of components. We use the following constraint system that operates on numeric lattice n only (rather than on (n , p ) pair):

n [l] F (s)(n [l ]) (30)
where we write n [l] (resp. n [l ]) for the numeric component of NumP at control point l (resp. l ), l being the control point of statement s, and (l , l) is an arc of the program control flow.

Example 4. Consider the Java snippet in Fig. 4. From l. 4 to l. 10 is the same as in the example program of Sect. 4. Since we do not propagate the points-to graph here, the state at l. 10 is the numeric lattice n 0 :

n 0 = {δ h,val → [-17, 41], i → 42, max → , n → } (31)
where three scalar variables i, max and n as well as a summarized variable δ h,val are involved. Note that the flow-insensitive points-to graph

p f i = tmp hd cur / / h next Q Q (32)
is used in the process of propagation of states but the points-to graph itself will keep unchanged (as formalized in ( 30)). From l. 14 to l. 21, the program finds the maximal value from the list. This value is then stored in the variable max.

In case there is no positive value or the list is empty, max takes its initial value 0. We will show that at the end of the program, (l. 10):

the scalar value max has to be in the range of [0, 41]

The propagation of states from lattice n 0 is shown in Fig. 5.

1 / / c r e a t e a l i s t o f i n t e g e r s 2 L i s t hd = null , cur , tmp ;

3 i n t i , n , max ; 4 f o r ( i = -1 7 ; i < 4 2 ; i ++){ 5 L i s t tmp = new L i s t ( ) ; / / h 6 tmp . v a l = i ;

Experiments

We have implemented a prototype for the abstract domain NumP . The implementation is called NumP. This section presents the prototype and our experimental results.

The input Java program is passed to SOOT. It computes the points-to graph and transforms the program to Jimple IR [START_REF] Vallee-Rai | Jimple: Simplifying java bytecode for analyses and transformations[END_REF]. The analysis combines the abstract domains from PPL and the points-to analysis in SOOT. It infers numeric properties for each program point of the IR.

The analyzer NumP combines PPL and SOOT in a modular way. We first implement the traditional static numeric analyzer for Java. The implementation is denoted by Num, which is implemented by wrapping abstract domains in PPL. Num either skips unrecognized statements or conservatively approximates them using the unconstraint operator in PPL. The re-used components in SOOT include notably the flow-insensitive points-to analysis (from its SPARK toolkit [START_REF] Lhoták | Scaling Java points-to analysis using Spark[END_REF]). This analyzer is denoted by Pter subsequently.

To demonstrate the effectiveness of our technique, we evaluate the analyzer on Dacapo-2006-MR2 [START_REF] Blackburn | The DaCapo benchmarks: Java benchmarking development and analysis[END_REF] benchmark suite. The experiments were performed on a 3.06 GHz Intel Core 2 Duo with 4 GB of DDR3 RAM laptop with JDK 1.6. We tested all 11 benchmarks in Dacapo.

Experimental results are shown in Tab. 1 using the interval domain Int64 Box from PPL and the flow-insensitive points-to analysis from SOOT. The characteristics of the benchmarks are presented by the number of analyzed Jimple statements (col. 2, STATEMENT) and the number of write access statements in the form of y p .f n = x n or y p .f n = k with k being a constant (col. 3, WA).

We measure PRCS (col. 4) for the number of the write access statements after which the obtained invariants are strictly more precise than Num. Q PRCS (col. 5) is the ratio of PRCS and WA Q PRCS PRCS/WA (33)

We record Q PRCS as the metric for precision enhancement of the analyzer. The execution time is measured for Num, Pter and NumP (col. 8, 9 and 10). The parameters T Num and T Pter are the times spent by Num and Pter when they analyze individually. The parameter T NumP records the time spent our combined analysis instantiated with the interval and flow-insensitive points-to analysis.

The last column Q T evaluates the time overhead of our analyzer. It is computed as the ratio of the time spent by our analysis to the total time spent by its component analyses.

Q T T NumP/(T Num + T Pter) (34)

The size of the analyzed Jimple statements ranges from 5, 197 (xalan) to 198, 541 (fop). The average precision metric is given in the last row of Tab. 1. The mean Q PRCS (25%) shows a clear precision enhancement of our approach over numeric analysis only. The time overheads Q T are generally acceptable.

In summary, we have designed an analysis in a modular way. It can be scaled to real-life programs; analyzing programs of hundreds of thousands of lines within hours can be a reasonable time budget for many applications. The precision enhancement is validated in practice.

Related Work

Static analysis of numeric properties has been extensively studied, especially in the framework of abstract interpretation [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF]. While a large number of articles covers issues related to numeric abstractions, program analyses where both pointers and numeric values are taken into account are comparatively few.

The back-end of CodePeer 2 takes a flow-insensitive may-aliasing analysis to distinguish heap objects and to transform the analyzed programs to their SSA forms using the global value numbering technique. The value propagation of CodePeer infers the value ranges of subtraction of variables, in other words, properties of the zone abstract domain. CodePeer goes further by taking care of inductive loop variables and the disjunctive numeric constraints, so that properties such as b > 0 ⇒ a = 2 * b can be inferred where a or b is an inductive scalar variable. Compared with our approach, however, CodePeer uses a single zone abstract domain and do not offer the flexibility to easily plug in other abstract domains of different precision/cost tradeoffs such as the more efficient interval abstract domain or the more precise polyhedral domain. In our approach, even the capability of expressing disjunctive facts in CodePeer can be easily implemented by instantiating our numeric domain component as the powerset construction domains [START_REF] Bagnara | A hierarchy of constraint systems for data-flow analysis of constraint logic-based languages[END_REF].

Efforts have been made to parametrize numeric domains with a dedicate pointer analysis. Fähndrich and Logozzo's Clousot analyzer [START_REF] Fähndrich | Static contract checking with abstract interpretation[END_REF] uses a value numbering algorithm to compute an under-approximation of must-alias. An optimistic assumption is then made so that Clousot regards two access paths not aliased if they do not have the same value numbering. 3 The ASTREE static analyzer [START_REF] Bertrane | Static analysis by abstract interpretation of embedded critical software[END_REF] relies on a type based pointer analysis to deal with numeric properties of heap objects. The abstraction can be used with pointer arithmetic, union types and records of stack variables in C programs that do not have dynamic memory allocation or recursive structure. This category of static analyzers, as well as ours, can be regarded as applications of the theory of abstract domain combination which has been thoroughly studied and applied in many other contexts [START_REF] Toubhans | Reduced product combination of abstract domains for shapes[END_REF][START_REF] Cousot | The reduced product of abstract domains and the combination of decision procedures[END_REF][START_REF] Cortesi | Combinations of abstract domains for logic programming: open product and generic pattern construction[END_REF].

A more sophisticated heap abstraction is shape analysis [START_REF] Sagiv | Parametric shape analysis via 3-valued logic[END_REF]. The TVLA [19] framework based on shape analysis uses canonical abstraction to create boundedsize representations of memory states. The analyses of this family are precise and expressive. TVLA users are demanded to specify the concrete heap using firstorder predicates with transitive closure, or user-defined instrumentation predicates like IsNotNull. Then TVLA automatically derives an abstract semantics based on the users' specification. The numeric abstraction of Gopan et al. [START_REF] Gopan | Numeric domains with summarized dimensions[END_REF] allows the integration of TVLA with existing numeric domains. The static verifier DESKCHECK [START_REF] Mccloskey | Statically inferring complex heap, array, and numeric invariants[END_REF] combines TVLA and numeric domains. It is sufficiently precise and expressive to check quantified invariants over both heap objects and numeric values. Besides the burden for users to specify the program (a problem that XISA [START_REF] Chang | Shape analysis with structural invariant checkers[END_REF][START_REF] Bor-Yuh | Relational inductive shape analysis[END_REF] attempts to remedy), the major issue of the shape-analysisbased approaches lies in their scalability. In contrast, our experiments show our capability to run over large programs.

Pioli and Hind [START_REF] Pioli | Combining interprocedural pointer analysis and conditional constant propagation[END_REF] show the mutual dependence of conditional constant analysis and pointer analysis. The combination is specifically designed for the conditional constant analysis and is not generalized to standard numeric domains. In particular, this approach does not directly cooperate with standard numeric domains because their method relies on the particular feature of conditional constant analysis that is able to partially eliminate infeasible branches.

In a somewhat different strand of work, numeric domains have been used to enhance pointer analysis. Deutsch [START_REF] Deutsch | A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations[END_REF] uses a parametrized numeric domain to improve the accuracy of alias analysis in the presence of recursive pointer data structures. The key idea is to quantify the symbolic field references with integer coefficients denoting positions in data structures. This analysis is able to express properties for cyclic structures such as "for any k, the k-th element of list l of length len, is aliased to its (k + len)-th element". Venet [START_REF] Venet | Towards the integration of symbolic and numerical static analysis[END_REF] develops the structure called the abstract fiber bundle to formalize the idea of embedding an abstract numeric lattice within a symbolic structure. The structure enables the using of the large number of existing numeric abstractions to encode a broad spectrum of symbolic properties.

Conclusion

The primary objective of this work has been the automatic discovery of numeric invariants in Java-like programs, which are generally pointer-aware. We have proposed a methodology for combining numeric analyses and points-to analysis, developed using an approach based on concepts from abstract interpretation. In particular, we have shown how the abstract domain used in points-to analysis can be used to lift a numeric domain to encompass values stored in the heap. The new abstract domain and the accompanying transfer functions have been specified formally and their correctness proved. Moreover, the modular way in which the abstract domains are combined via some well-defined interfaces is reflected in the modular construction of a prototype implementation of the analysis framework. This modularity has enabled us to experiment with different choices for the tradeoff between efficiency and accuracy by tuning the granularity of the abstraction and the complexity of the abstract operators. Concretely, the derived abstract semantics allows us to combine existing numeric domains (interval domains, octagon etc.) with existing points-to analyses. The modular analyzer is able to combine advanced libraries as PPL and SPARK and it shows a clear precision enhancement with low time overhead.

10 } 11 e l s e { 12 data= 13 data . v a l = -n ; 14 } 15 L 16 elem

 10111213141516 new Neg ( ) ; / / h 3 i s t elem = new L i s t ( ) ; / / h 4

10 δ h 3

 103

Fig. 1 :

 1 Fig. 1: An example in Java. The program passes an array of integers to a list of Unsigned numbers. Unsigned is a superclass of Pos and Neg. It has one field val of integer type. The class List has two fields, item of type Unsigned, and next of type List.

Fig. 2 :

 2 Fig. 2: A flow-insensitive points-to graph for the program in Listing 1.1.

Fig. 3 :

 3 Fig. 3: Structural Operational semantics -→ : Imp np → ℘(State × State)

  n = y p .f n Consider the snippet a = x.f; b = y.f; if (a < b) {...} Assume that p x.f ⇓ δ and p y.f ⇓ δ. It is tempting, but wrong, to abstract the semantics of a = x.f (resp. b = y.f ) as [|a = δ|] n (resp. [|b = δ|] n ) following which the analysis would incorrectly argue that the if branch can never be reached.

  ), are sound with respect to [|•|] : for any statement s of Imp np and abstract state (n , p ) of NumP , [|s|] •γ np (n , p ) ⊆ γ np • [|s|] (n , p ). We give a proof sketch for the case of [|x p .f n = y n |] . It is important to note that the soundness of the theorem is based on the soundness hypotheses of [|•|] n and [|•|] p . The combined analysis is sound as long as its component analyses are.

17 max = n ; 18 } 19 c 21 Fig. 4 :

 171819214 Fig. 4: An example in Java. The class List has val and next as fields.

Fig. 5 :

 5 Fig. 5: The propagation of states from l. 14 to l. 21 of the program in Fig. 4. The fixpoint is reached in two steps.

  A state in our proposed abstract domain is a pair (n , p ), where n is a numeric property expressed via scalar variables of Var n and summarized variables (see below) of the set H ×Fld n ; the element p is a lattice of Pter , namely, a points-to graph in our context. Definition 4 (Summarized variable). A summarized variable is a pair of an abstract reference h ∈ H and a numeric field f n ∈ Fld n . The set of summarized variables is denoted by ∆.∆ H × Fld n (13)We will use the meta-variable δ to range over the pairs in ∆, or we write δ h,fn to indicate the summarized variable corresponding to (h, f n ).

Definition 5 (The abstract domain NumP ). The abstract domain NumP is defined to be NumP Num [∆ ∪ Var n ] × Pter (14) Below, we specify the concretization function. It consists of an essential step before defining and proving the correctness of the abstract operators on NumP . Revisit the example in Sect. 3. We have obtained the state (n , p ) at the end of the program, with

Table 1 :

 1 Evaluation of NumP on the benchmark suite Dacapo-2006-MR2

	Benchmark Characteristics	Precision	Time
	BENCHMARK STATEMENT WA PRCS Q PRCS T NUM T PTER T NUMP Q T
	antlr	26776 766	174	23% 00m29s 00m53s 01m36s 117%
	bloat	64328 2472	943	38% 01m35s 01m02s 16m33s 632%
	chart	132627 10244 3690	36% 04m17s 13m20s 83m21s 473%
	eclipse	56772 820	116	14% 00m46s 00m54s 01m52s 112%
	fop	198541 23482 6166	26% 03m25s 05m11s 275m28s 3203%
	jython	88302 2583 1356	52% 00m57s 01m04s 05m38s 279%
	hsqldb	6286 352	10		3% 00m19s 00m49s 01m16s 112%
	luindex	22192 1206	250	21% 00m33s 00m54s 01m31s 105%
	lusearch	26711 1503	418	28% 00m38s 00m56s 01m35s 101%
	pmd	80640 3675 1316	36% 00m50s 00m55s 04m25s 252%
	xalan	5197 341	3		1% 00m16s 00m49s 01m12s 111%
	Mean	64397 4313 1313	25% 01m17s 02m26s 35m52s 500%

The research leading to these results has received financial help from AX -L'Association des Anciens Élèves et Diplômés de l' École polytechnique. 5, rue Descartes 75005 PARIS.

This term is used here to be distinguished from basic statements as sn, sp or snp. Note that sn is the assertion, not the whole if-statement.

http://www.adacore.com/codepeer

This assumption is said optimistic because it is possible two access paths alias at run-time but are considered never aliased by Clousot.

Acknowledgments. The author wishes to express his gratitude to Thomas Jensen, Laurent Mauborgne and David Pichardie for their thoughtful feedback.


Jaume Ferrarons

Mulu Adhana

Carlos Colmenares

Sandra Pietrowska

Fadila Bentayeb

Jérôme Darmont

PRIMEBALL: a Parallel Processing Framework Benchmark for Big Data Applications in the Cloud

Keywords: Benchmark, Cloud Computing, Parallel Processing Framework, Big Data, Real

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

We are currently living through an information revolution that has undoubtedly brought a massive increase in the volume of data being produced and stored worldwide. In this Internet age, where the world creates 2.5 exabytes of data every day [START_REF]What is big data[END_REF], traditional approaches and techniques for data analysis proved limited because some lack parallelism, and most lack fault tolerance capabilities. Therefore, in recent years, many platforms for parallel processing have been created so as to satisfy this need. These platforms provide frameworks for storing, accessing, updating and deleting data efficiently in computer clusters, ensuring fault tolerance and making the whole process transparent to users. Examples of such systems include Google's BigQuery [START_REF] Sato | An Inside Look at Google BigQuery[END_REF] and Apache's Hadoop [START_REF] Shvachko | The Hadoop Distributed File System[END_REF].

In this context, the terms "big data" are used for referring to digital information that comes in high volume, velocity and variety [START_REF]What is big data[END_REF]; and the systems that make use of this type of data for achieving profitable objectives can be referred to as big data applications. Several examples of big data applications can be found in the areas of capital market, risk management, retail, social media analysis and meteorology. This kind of applications, beside requiring high parallel processing capabilities for analysis, also needs a good and scalable infrastructure capable of adapting quickly to an increment in computing or storage needs. Therefore, many big data applications are being deployed in the cloud so as to allow fast adaptability and flexibility.

Given the recent increase of big data applications in the cloud, and the use of parallel processing frameworks for dealing with the technical issues implied by the use of clusters and large amount of complex data, it has become important to fix standards so as to allow accurate comparisons of these frameworks. Several benchmarks already exist for measuring a system's parallelization capabilities, cloud features or big data analysis abilities, but none of them offers direct means of accurately measuring: 1) the three of them 2) in a real-life context. Thus, following the principles defined by Folkerts et al. [START_REF] Folkerts | Benchmarking in the Cloud: What It Should, Can, and Cannot[END_REF], we propose the specifications of PRIMEBALL to position it as a complete and unified benchmark for assessing a system's performance w.r.t. two main axes involved in the context of big data applications hosted in the cloud: parallel processing frameworks and cloud computing service providers. PRIMEBALL also aims to emulate common usages of cloud services, data manipulations and data transfers.

The remainder of this position paper is organized as follows. Section 2 reviews existing benchmarks similar to PRIMEBALL and motivates its design. Section 3 provides an overview of PRIMEBALL. Then, Sections 4, 5 and 6 detail the specification of PRIMEBALL's components, i.e., its dataset, workload, and properties and metrics, respectively. Finally, Section 7 concludes this paper and provides future research leads.

Related Work

Among the standard TPC benchmarks, TPC-DS, a decision support benchmark that models several generally applicable aspects of a decision support system, including queries and data maintenance [START_REF]Transaction Processing Performance Council (TPC)[END_REF], is closely related to data analytics we target at. However, although it can generate high volumes of data, its underlying business model is a classical retail product supplier, thence its dataset could not fully qualify as big data-oriented because of a lack in structural variety.

MalStone is benchmark for data intensive computing and analysis [START_REF]Generate synthetic site-entity log data for testing and benchmarking applications requiring large data sets[END_REF]. It features MalGen, a synthetic data generator that produces large datasets to perform benchmarking. Data is designed to assess systems from the parallel processing point of view. Data is generated probabilistically following specified distributions.

Cloud Harmony measures the performance of cloud providers as black boxes [START_REF]Cloud Harmony[END_REF]. The tests performed are mainly focused on assessing hardware performance or specific technologies. Cloud Harmony actually aggregates the results of benchmarks that existed before.

The Yahoo! Cloud Serving Benchmark (YCSB) is a framework to facilitate performance comparisons among cloud database systems [START_REF] Cooper | Benchmarking cloud serving systems with YCSB[END_REF] that mainly focuses

The first property we compare is whether the data processed by a benchmark is produced artificially or extracted from a real environment. Only PRIMEBALL offers the possibility to work with wholly real data, with the aim to better simulate real applications including facets of the problem difficult to emulate when using random distributions to produce data. Although some of the benchmarks used in Cloud Harmony do use real data, most of them are actually processing artificial data. There are also in between positions such TPC-DS which produces data artificially but trying to follow the structure of a real environment. Proposing a real workload is the second property we selected. A benchmark system bearing this property is executing real-world operations to better simulate a production environment. PRIMEBALL, SWIM and TPC-DS execute only tasks that are closely related to real-world workloads. Moreover, some benchmarks in Cloud Harmony also execute tasks that are common in real environments but not all, for that reason has been marked with a tilde.

The next property is satisfied by all analyzed benchmarks, i.e., they are all aimed at assessing parallel processing. By contrast, Cloud Harmony is the only benchmark that assesses the performance of specific pieces of hardware. For example, it has benchmarks for measuring CPU performance, memory I/O and disk I/O. The other benchmarks can give a notion of the performance of specific parts of the hardware, but are not that specific.

The MapReduce-related property refers to benchmarks aiming at measuring the quality of a system in terms of the performance obtained when executing MapReduce tasks. SWIM is the only benchmark that is uniquely dedicated to MapReduce. However, if PRIMEBALL is implemented using MapReduce tasks, it can measure performance through them too. Cloud properties refer to the prominent features of cloud computing. All benchmarks but TPC-DS and Cloud Harmony are designed to measure properties such as vertical and horizontal scalability, consistency, etc. (cf. Section 6.1). Even though TPC-DS can be used, e.g., to measure the scale up of a distributed SQL database but it is not its purpose. On the other hand, PRIMEBALL has been designed as well to be able to assess this kind of properties.

Complex data properties describe the benchmarks that are oriented to execute procedures using complex data structures to assess the system under test (SUT). TPC-DS implements a classical data warehouse with numerical and textual values. MalStone only aims to generate a big dataset as a log file and measures system response while processing it, thus the data processed is not complex. The same is true for YCSB, which assesses the performance of keyvalue stores. Values can be complex, but they are not processed, only stored. The other benchmarks, including PRIMEBALL, include complex data in some of their procedures. Big data properties describe the benchmark systems that involve analytical aspects over large amounts of data. All benchmarks have analytical situations involving large amounts of data. PRIMEBALL has specifically been designed to satisfy this property. TPC-DS has been marked with a tilde because it can be used for this purpose but it depends mainly on the size of data used.

Finally, technology independence describes the systems the are designed to work with several kinds of technologies. YCSB and SWIM do not fulfill this property, because YCSB is oriented to analyze the performance of key-value stores only; and SWIM only assesses MapReduce procedures, and thus only makes sense when the SUT is able to execute them. The other benchmarks, including PRIMEBALL, can be used in environments that are not constrained by a given technology.

PRIMEBALL Overview

Application Model

PRIMEBALL's contextual application is set around New Pork Times: a fictitious on-line information service including international news, current affairs, documentaries, science, health and lifestyle sections. It is constantly updated and available 24-hours all around the world. New Pork Times hosts articles and multimedia documents about the latest news, as well as a large archive of past information.

All of these data are stored in a system called New Pork Times' News Hub (NPT-NH), which resides in a cluster hosted by some cloud service provider. This cluster is managed by a framework for parallel data processing and provides a remote storage that allows the user to access the files in the cluster without having to worry about their distribution in nodes. This storage system allows the user to insert and update data, and also to execute batch processes for analyzing/processing the data.

PRIMEBALL Features

This section lists what PRIMEBALL is/does and does not, so that its position, notably w.r.t. state of the art benchmarks (Section 2), is clear.

On one hand, PRIMEBALL:

is a benchmark. It aims to compare the performance of the parallel processing framework under test with respect to several meaningful metrics; -is cloud-oriented. The obtained results could also be used to compare:

• cloud platforms as parallel processing frameworks,

• service providers executing systems using the same cloud platform; -is repeatable. All the proposed experiments are designed to lead to the same results if they are executed under the same conditions; -is portable. The benchmark has been designed to be implemented in different cloud platforms. -does define a set of operations that is meaningful in the context of parallel processing and cloud computing; -does define performance metrics that are oriented to measure cloud properties. The criteria to assess each metric are also defined; -does define data relationships. We provide a description of the information stored in the SUT to be processed during the benchmark run.

On the other hand, PRIMEBALL does not:

define technical execution details. It defines guidelines, but given that SUTs can be very different, the relevance of results is tightly related to implementation details; -define expected performance results. No absolute value is provided as a comparison point, given that they are subject to implementation details; -compare data retrieval or processing algorithms; -define a storage schema. However, we define how data are physically stored.

Thence, PRIMEBALL is the first cloud-oriented unified benchmark aiming to assess all the elements involved in cloud-based big data application systems.

PRIMEBALL Dataset

For using PRIMEBALL, it is necessary to implement NPT-NH (Section 3.1). Therefore, the following subsections contain a technical description of its architecture, the type of data it contains and the operations performed onto data by means of batch processes, such as metadata extraction.

Types of Files to be Hosted

The system's database shall hold only three types of files. However, there can be many files of the same type. The three types of files follow.

-General information (XML): This set of files comprise the many XML documents that describe the standard information stored by NPT-NH, i.e., information about authors, the actual news, and so on. Section 4.2 describes the conceptual schema of this information. -Media files (binary): Some articles make references to these files, which can be either audio or video documents. -Metadata (XML): Several metadata for information retrieval and other tasks are extracted from the other two types of files by internal algorithms, for further querying. These metadata must be persisted as XML files in the system.

PRIMEBALL Schema

The system must hold as XML files data about the following entities:

articles: the actual news articles; -topics: the topics an article may belong to; -keywords: sets of words that roughly describe the content of an article; -languages: marks for indicating what language/dialect an article is written in; -authors: people who write the articles; -journalists: authors who work in journals and make interviews; -professionals: specialists in some topic who write special analyses; -countries: information about countries authors might be citizens of or work in; -dates: information about the day of the year when an article was written; -media: reference to a media file with some internal comments.

The conceptual schema of this dataset is featured in Figure 1. Its actual implementation depends on the framework for parallel data processing to be benchmarked and its capabilities for storing data.

Initial Data

To create an initial corpus for populating NPT-NH, PRIMEBALL shall come bundled with a crawler that extracts, transforms and loads information from one or more real world news hub akin to New Pork Times (a famous news site may come to mind). The crawler fetches information about news published during a requested period of time, which is recommended to be set up as the last 40 years. Moreover, it must also extract information about authors, media files available, and metadata about the articles relevant to the system's architecture. Due the big data properties of the benchmark, it is recommended to fetch at least Once the corpus has been fetched, it can be sliced at will for selecting any scale factor for the initial data population. However, it is important to bear in mind that if the whole corpus is used in the initialization phase, then it will not be possible to perform updates or scale operations, since there will not be extra data available.

Metadata Processes

When data are loaded, it is necessary to run algorithms that extract some metadata from the files and build the structures for the following information retrieval tasks performed by NPT-NH:

run a Hidden Markov Model [START_REF] Juang | Hidden Markov models for speech recognition[END_REF] speech recognition algorithm on media files for transcribing the speech to text; -compute the TF-IDF measure for all articles and transcriptions, as specified in the CDI IDF algorithm [START_REF] Xu | A Refined TF-IDF Algorithm Based on Channel Distribution Information for Web News Feature Extraction[END_REF]; -compute the page rank of articles, as specified in the weighted pagerank algorithm [START_REF] Wing | Weighted pagerank algorithm[END_REF]; -perform a topic extraction routine on articles and transcriptions, as specified in the Latent Dirichlet Allocation algorithm [START_REF] Newman | Distributed algorithms for topic models[END_REF].

These algorithms have to be implemented as described in the cited references and adapted to be run in the cluster managed by the parallel data processing framework.

Data Scaling and Maintenance

This section describes the processes performed for updating and scaling data in NPT-NH. Basically, these processes are executed integrally as batch tasks. New Pork Times' authors write new articles every day. Articles have to be placed in NPT-NH for allowing access to users. New authors may also come in. The following scaling tasks have to be performed by the system. New data has to be obtained as progressive slices of PRIMEBALL's corpus, making sure that the data was not already inserted. Once new data are inserted, the system has to extract the necessary metadata from them so as to ensure that subsequent queries can be performed.

More specifically, when new information is inserted, it is necessary to recalculate some structures used for information retrieval. Thus, PRIMEBALL contains an implemented procedure for recomputing both TF-IDF metrics from all the documents and topics for all articles.

PRIMEBALL Workload

Query Set

This section contains the set of queries that are typically performed by NPT-NH users and that must be used for testing the performance of any given parallel data processing framework. These queries must be performed over the dataset defined in Section 4 and involve the most important aspects of performance. Although the following set of queries is not finite, it covers a wide range of classes from Figure 1, the relationships between them; it is applicable and enables to successfully measure performance.

One first subset of queries concerns the most common and hottest topics published in the system. The user might be interested in this information in order to know what kind of issues are the most frequently described in a certain interval of time, and therefore attract attention. 7. Articles published on date D with the greatest number of references to the previous year. 8. Articles related to a topic T very frequently referenced lately, i.e., in a time interval I ending at the current date. 9. Journalists and professionals who wrote an article on the same month, on the same topic, sorted by days.

Finally, to analyze the diversity of articles and compare them w.r.t. their source, one should consider the following, eventual group of queries. 10. Articles written by X journalists in a specific time interval I that have at least Y common topics. 11. Rank of the languages in which articles are written. The output consists in pairs (language, number of articles). 12. Articles written by an author A from a given country C that best match a search term S. 13. Documents that best match another document published on the same day and month, but one year later. 14. Articles that focus on the same topic, but have been written by different journalists who were born before and after a given year Y .

Test Protocol

We present in this section different scenarios to help actually benchmark a system. To define them, a default scale factor SF is used. A dataset of scale factor SF is a set of articles and corresponding metadata having a total size of SF GB.

Scenario 1 This scenario simulates the evolution of the system along time, in terms of data operations and queries.

Initial state

The system contains a dataset with a specified scale factor SF .

Operations

1. Execute queries 4, 7 and 14 from the generic query set (Section 5.1) choosing as date, e.g., September 12, 2001. 2. Double the volume of the dataset according to scenario 7. 3. Repeat the queries executed in step 1, for the same date and another one, e.g., November 5, 2008.

Scenario 2 This scenario simulates an extreme situation: a very famous article has been published with many mistakes and publishers are correcting it constantly. Their main concern is to deliver a consistent view of the article to people. Here, we are interested in measuring how many times the article is read in the older versions after being read once in the new version.

Initial state

The system contains a dataset with a specified scale factor SF .

Operations

1. Initiate a thread performing 100 queries per second to retrieve the given article. 2. Start another thread updating the same article every 5 seconds.

Scenario 3 This scenario simulates node failures in terms of network reachability. Here, we are interested in knowing how many nodes can be removed from the cluster before some data become unreachable.

Initial state

The system contains a dataset with a specified scale factor SF .

Operations

1. Execute all queries from the generic query set (Section 5.1) sequentially. 2. Remove a node and reiterate step 1.

Scenario 4 This scenario aims to measure the concurrency offered by the system while accessing data.

Initial state

The system contains a dataset with a specified scale factor SF .

Operations Execute the following process 300 times and count the number of inconsistencies.

Scenario 5

The objective of this scenario is to simulate analysis procedures over the dataset.

Initial state

The system contains a dataset with a specified scale factor SF .

Operations Execute queries uniformly selected from the following.

1. Top 10 articles seen each month in 2010.

2. Average number of pages per article for each journalist in the system. 3. Average age of publishers and standard deviation. 4. Maximum number of versions of an article.

Scenario 6

The aim of this scenario is to initialize the system and make it ready for handling the information for New Pork Times.

Initial state Empty storage system.

Operations Execute the steps described in Section 4.3 to initialize the environment.

Scenario 7 This scenario is used to increase the volume of the dataset to simulate the fact that new articles are inserted over time.

Initial state NPT-NH has a consistent state.

Operations Execute the steps described in Section 4.5 for data scaling and maintenance.

PRIMEBALL Properties and Metrics

Properties and Performance Metrics

This section presents the metrics that we use to evaluate the performance of the SUT. We also define the different system properties that can be assessed using PRIMEBALL.

We first specify two main metrics. The first one is throughput. The throughput of the SUT for a given scenario is the total time required to execute it (scenarios are defined in Section 5.2). The second metric, price performance, takes price (Section 6.2) into account and is expressed as follows.

Price performance = Throughput P rice

Moreover, the set of operations that can be executed against the system in the context of New Pork Times is defined as follows.

-Read: Obtain one or more articles. Using all these definitions, we can set the following properties.

Generic Cloud Properties

1. Scale up: ability of the system to handle more data when adding more computers while maintaining performance.

-Importance: In the case of a news website, it is very important to be able to scale up the system. There are a lot of news added every day and the service must keep on performing the same. -Measurement : To measure this property, scenarios 4 and 5 (Section 5.2) must be executed twice, doubling the amount of data (SF ) and the amount of nodes in the cluster the second time. Throughput increase ratio is the metric recommended for this property.

Throughput increase ratio = Throughput after Throughput before 2. Elastic speedup: adding more computers to the cluster with the same amount of data results in better performance.

-Importance: For New Pork Times, it is very relevant to know whether the system can offer a better performance when required, e.g., when there is a worldwide event with more people involved than usual looking for news and information. Thus, it is crucial to be able to maintain the quality of service even during peak demands. -Measurement : To measure this property, we propose to execute scenarios 2, 4 and 5 (Section 5.2) in order to observe throughput with the default cluster SF size. The metric we propose is also throughput increase ratio.

Throughput increase ratio = Throughput after Throughput before 3. Horizontal scalability: ability of the system to distribute evenly the data load and workload among cluster nodes.

-Importance: It is very useful to know up to what point one can exploit the current cluster and keep throughput in between some boundaries.

In other terms, we determine what highest price performance can be achieved. It is very interesting in two senses:

• upper bound: to answer the question "how many articles can the news website add into the system while keeping response time below 0.2 seconds";

• lower bound: to optimize resource usage while fixing a performance lower bound. It might indeed be possible to reduce the number of nodes and offer the same user experience (response time). -Measurement : To assess this property, scenarios 4 and 5 (Section 5.2) must be executed and system throughput measured. Then, SF is increased and the process repeated. Again, throughput increase ratio can be used to evaluate this property. The closer it is to 1, the better is horizontal scalability.

Throughput increase ratio = Throughput after Throughput before 4. Latency: time to execute a set of operations.

-Importance: For New Pork Times, it is essential to be able to show news very quickly to users. If it takes too much time, users are going to look for a different website, thus a low latency is required. -Measurement : Latency of the SUT can be measured as the throughput when executing scenarios 4, 5 and 6 (Section 5.2).

5. Durability: ability of the system to retain information for a long period of time.

-Importance: In the case of a news website, it is very important to ensure that no information is lost. Users have to be able to check and find information they have read previously. -Measurement : Scenario 1 (Section 5.2) is intended to measure data durability. We define the durability ratio as a metric for this purpose.

Durability ratio = Correct reads Total reads 6. Consistency and version handling: two different readings of the same data at the same time should return the same value.

-Importance: It is important for a website to give a consistent view of data to all users at the same time around the world. In the proposed model, There may be several revisions of an article, which has to be consistent for all readers. -Measurement : Using scenario 2 (Section 5.2), the performance of the system for this property can be measured using the consistency ratio as a metric.

Consistency ratio = Consistent reads Total reads 7. Availability: data is accessible even when there are some inaccessible nodes.

-Importance: It is very relevant for New Pork Times to guarantee the access to all the news stored in the system. -Measurement : Scenarios 3 and 6 (Section 5.2) aim to measure this property, thus the throughput of the SUT can be taken as a metric for this property.

8. Concurrency: the system has to be able to offer a service to different clients at the same time.

-Importance: In New Pork Times, users can keep reading while publishers are adding news, and the system has to be able to handle the multiple operations of different natures at the same time. -Measurement : Given concurrent scenario 4 (Section 5.2), we propose two metrics:

• system throughput;

• concurrency ratio.

Concurrency ratio = Successful operations Total operations

Complex Data Properties 9. Path traversals: ability of the system to link data from different parts of the schema using the defined relationships.

-Importance: In the case of a news Web site environment, this property is very important to improve search experience. -Measurement : Queries 3, 4, 7, 10 and 12 (Section 5.1) from the generic query set involve following a path through different class relations to link concepts. The throughput of this type of queries is used to measure that property. 10. Construction of complex results: ability of the system to generate (semi)structured output from the information system.

-Importance: This property is very relevant to a news website, mainly to allow analysis over the contained data. -Measurement : The generic query set defined in Section 5.1 contains queries with complex results, i.e., queries 2, 3, 6 and 11. The throughput of these queries can be used as a metric for this property. Moreover, scenario 6 (Section 5.2) has to be used to measure this property. 11. Polymorphism: ability of the system to deal with type inheritances, i.e., treating types and subtypes of objects to compute query results.

-Importance: Inheritance is a good way to deal with complex relationships between objects. For this reason, the performance of the system while executing these kinds of operations is very relevant. -Measurement : Fix a cluster and an initial workload, then execute and measure system performance while executing queries 3, 9, 12 and 15 (Section 5.1; all of them involve inheritance operations).

Big Data Properties 12. Analysis: ability of the system to generate summarized data and statistical information.

-Importance: For a news website, having statistics such as how many times an article has been read, average words per article, etc., is very relevant.

-Measurement : This property can be measured in terms of throughput while executing analytical scenario number 5 (Section 5.2).

Information Retrieval Properties

13. Full text: being able to search a single word in all documents simultaneously.

-Importance: This property is very relevant to a news website to allow users searching information easily in the system. -Measurement : It can be measured in terms of throughput when searching for different terms, some famous, some normal and some strange, e.g., Obama, Higgs, Star Trek, Cleopatra, etc. Queries of this type are included in the generic query set (Section 5.1).

Pricing

In Section 6.1, we defined sytem performance w.r.t. time and cost. The main pricing factors involved in processing data in the cloud follow.

-Cloud provider: different cloud service providers may have different pricing policies. -Number of instances and type: infrastructure used to execute PRIMEBALL.

-Required storage space: it is directly related to the scale factor used (Section 5.2). -Platform inherent costs: operation, administration and maintenance.

-Execution time: time spent to run the tests.

The specific cloud provider model has to be applied to compute real cost.

Conclusions

We propose in this paper the specifications for PRIMEBALL, a complete and unified benchmark for measuring the characteristics of parallel cloud processing frameworks for big data applications. In front of the already existing benchmarking options, PRIMEBALL can be used as a guideline to build an integral solution for benchmarking could platforms. The real-life model adopted in PRIMEBALL is that of a fictitious news hub called New Pork Times, which is basically a fair approximation of a popular real-life news site. The general architecture and inner processes of the system are well-defined so as to allow an unambiguous implementation of the benchmark.

The workload applied on this news dataset is not only made of queries, but also of data-intensive batch processes. Moreover, we propose several use-case scenarios together with relevant metrics for assessing the framework's performance from different points of view, such as data availability or horizontal scalability. The novelty of our work lies in the fact that existing, related benchmarks measure parallelization capabilities, cloud features, big data analysis ability, but none of them combines all these properties while exploiting real-life data.

Future work on PRIMEBALL will be mainly focused on implementing a crawler for fetching and transforming real data from the Web to feed the benchmark's dataset. Distributing the built dataset online will improve the repeatability of the experiments. Moreover, the actual feasibility and relevance of PRIME-BALL shall be validated by actually implementing the benchmark in several cloud environments to obtain experimental results and by publishing performance comparison results. For instance, implementation in popular data processing frameworks such as Hadoop should be achieved.

Moreover, future extensions of the benchmark could include new scenarios that exploit different properties of cloud providers, such as vertical growth of the cluster, or new measures such as efficiency of bandwidth use. Actual experiments should also help refine the benchmark's workload.

Fig. 1 .

 1 Fig. 1. Conceptual Schema of PRIMEBALL's Dataset

1 .

 1 Articles containing the most frequent bigrams, sorted by pagerank. 2. Articles published during a time interval I, sorted by topics. The output contains pairs of article title and topic. 3. Most frequently used words by a journalist J from each country in the world during a certain time interval I. The output is compound by a list of countries, each one with keywords. 4. Rank of the keywords used in the articles published on an exact date D. 5. Most frequently used keywords in month M and year Y .

Furthermore, in order

  to evaluate how topics evolve w.r.t. time, it is necessary to include the various time measures in a second subset of queries. 6. Most frequently used keywords on day D and two different years Y 1 and Y 2 , sorted by descending count.

1 .

 1 Start 10 threads executing the whole generic query set (Section 5.1). 2. Start 5 threads each of them performing: (a) updates in articles: 10 per second; (b) removing articles: 10 per second; (c) adding articles: 10 per second.

-

  Write: Create a new article or a new version, add new journalists, languages, topics... -Update: Modify an existing article within the same version or modify the information related to a journalist. -Delete: Remove inappropriate content. -Search: Obtain articles by matching a search (a set of given words, topics, authors, dates...).

Yes Yes

Yes Yes Yes Technology-indep


Sonia Boscolo
email: s.a.boscolo@aston.ac.uk

Christophe Finot

Huseyin Karakuzu

Periklis Petropoulos

Pulse shaping in mode-locked fiber lasers by in-cavity spectral filter

We numerically show the possibility of pulse shaping in a passively mode-locked fiber laser by inclusion of a spectral filter into the laser cavity. Depending on the amplitude transfer function of the filter, we are able to achieve various regimes of advanced temporal waveform generation, including ones featuring bright and dark parabolic-, flat-top-, triangular-and saw-tooth-profiled pulses. The results demonstrate the strong potential of an in-cavity spectral pulse shaper for controlling the dynamics of mode-locked fiber lasers.

Passively mode-locked fiber lasers have generated major interest as an alternative to solid-state systems owing to improved simplicity, stability and cost. In general, they rely on nonlinear processes to achieve mode-locking, and major steps forward in pulse energy and peak power performance have been made with the recent discovery of new nonlinear mechanisms of pulse generation [1], namely, dissipative solitons in all-normal-dispersion cavities and parabolic self-similar pulse (similariton) propagation [2][3][4][5]. These are qualitatively distinct from the well-known soliton and dispersion-managed soliton (stretched-pulse) regimes. Further, the possibility of triangular and parabolic pulse shaping in mode-locked fiber lasers using nonlinear dynamics was reported in [6]. In relation to the work presented here, a spectral filter was used in [3] to initiate the transition from similariton evolution in the gain fiber segment of the laser to soliton evolution in an anomalous-dispersion segment by undoing the spectral broadening of the amplifier similariton. A strong spectral filter that compensated for the broad pulse duration and bandwidth after the gain segment provided the main mechanism for seeding similariton evolution in the amplifier in the all-normal-dispersion cavity demonstrated in [4]. From a fundamental standpoint, fiber lasers provide convenient and reproducible experimental settings for the study of the dynamics of dissipative systems. Thus far however, mode-locked fiber lasers have been relatively limited in terms of their reconfigurability, and achieving different output pulse characteristics generally involves significant changes to the physical layout of the cavity.

Spectral pulse shaping [7] is a technique which employs spectral manipulation of the intensity and phase components of a pulse, in order to create the desired field distribution at the output of a mode-locked laser. It has been highly successful for applications in a number of fields [8,9]. However, since the pulse shaper is normally placed outside the laser cavity, it requires careful alignment between the wavelength of the shaping filter and the emission wavelength of the laser, and its control of the laser field is limited; the bandwidth of the filtered spectrum is determined by the bandwidth of the input spectrum, and manipulation of the in-cavity dynamics of the laser is not possible. In addition, the pulse shaper can only subtract power from the frequency components of the signal while manipulating its intensity, thereby potentially making the whole process extremely power inefficient. The inclusion of a pulse shaper into the cavity of a passively mode-locked fibre laser was recently demonstrated [10], allowing for tunability of the wavelength and operation at high repetition rates. In [11,12], the phase filtering ability of an in-cavity pulse shaper was shown to enable precise control of the cavity dispersion of the laser as well as to change the output pulse train from bright to dark pulses. In this Letter we take advantage of the amplitude and phase filtering ability of an in-cavity spectral pulse shaper to numerically show the possibility to achieve different pulse-shaping regimes in a mode-locked fiber laser. By changing the amplitude profile applied to the filter, we are able to create various output temporal waveforms of fundamental and practical interest, ranging from bright and dark parabolic profiles to a flat-top profile, and triangular and saw-tooth (asymmetric triangular) profiles [13].

The cavity configuration considered is a simple ring cavity as shown in Fig. 1. The gain is provided by a 1 m-long segment of ytterbium-doped fiber (YDF) with normal group-velocity dispersion (GVD), while 6 m of single-mode fiber with normal GVD [normally dispersive fiber (NDF)] acts as the nonlinear element of the cavity. A saturable absorber (SA) element follows the gain fiber, and an amplitude and phase filter is placed between the passive fiber and the amplifier to realize the pulse shaping. Propagation within each section is mod- eled with a modified nonlinear Schrödinger equation for the slowly-varying pulse envelope:

ψ z = - iβ 2 2 ψ tt + iγ|ψ| 2 ψ + 1 2 g ( ψ + 1 Ω 2 ψ tt ) , ( 1
)
where β 2 = 25 fs 2 /mm is the GVD and γ = 0.005 (W m) -1 is the coefficient of cubic nonlinearity for each fiber section [2]. The dissipative terms in Eq.

(1) represent linear gain as well as a parabolic approximation to the gain profile with the bandwidth Ω corresponding to 40 nm full-width at half-maximum (FWHM) bandwidth. The gain is saturated according to g = g 0 /(1 + W/W 0 ), where g 0 = 35 dB/m is the small-signal gain which is nonzero only for the gain fiber, W = ∫ dt |ψ| 2 is the pulse energy, and W 0 = 150 pJ is the gain saturation energy determined by the pump power. The SA is given by a monotonically increasing transfer function T = 1 -q 0 /[1 + P (t)/P 0 ], where q 0 = 0.9 is the unsaturated loss, P (t) is the instantaneous pulse power, and P 0 = 150 W is the saturation power. The filter is modeled by the spectral response Ĥ(ω) = ĥ(ω) exp

( iβ 2,acc ω 2 /2 )
, where ĥ(ω) denotes the Fourier transform of a certain objective waveform function h(t), and the spectral phase adds a specific amount of GVD to the cavity. By varying the curvature β 2,acc (in ps 2 ) of the parabolic phase function we can control the net dispersion of the cavity. We consider the generation of five different amplitude functions in our study, which represent some examples of interesting optical waveforms. We use a bright parabolic pulse shaper with

h(t) = √ 1 -(t/τ ) 2 θ (τ -|t|), τ = 1 ps; a dark parabolic pulse shaper such that h(t) = (1 -|t/τ |) θ (τ -|t|) with τ =
(t) = √ 1 -t/τ in t ∈ [0, τ ], h(t) = 0
otherwise, with τ = 2 ps. Here θ(x) is the Heaviside function. Note that the spectral filter can be realized in a variety of ways, such as a fiber Bragg grating or even a programmable Liquid Crystal on Silicon optical processor, which offers the additional ad- vantage of being easily reconfigurable [14]; such devices are already commercially available. The output of the laser is monitored behind 70% and 10% couplers at the output of the pulse shaper and just after the gain segment, respectively. The numerical model is solved with a standard symmetric split-step propagation algorithm, and the initial field is a picosecond Gaussian temporal profile.

The solutions obtained for the different amplitude profiles applied to the filter and net GVD of 0.008 ps 2 are shown in Fig. 2. It is seen that the desired pulse shapes are obtained at the output of the filter. In the case of flat-top and saw-tooth waveform functions, because of the sharp edges of these pulse shapes an additional Gaussian bandpass filter with a FWHM bandwidth of 2 THz is included in the pulse shaper to make the top of the resulting pulse ripple-free and to smooth the formed pulse shape, respectively. The generated parabolic and triangular pulses are nearly transform-limited, whereas the flat-top pulse features a small positive chirp. We can also see from Fig. 2 that, as opposed to the chirp profile targeted by the filter, the chirp profile of the generated pulses may exhibit a small ripple. This indicates that generating pulses with a well defined phase profile by use of the method proposed in this Letter is not as straightforward. Figure 2 also highlights that the temporal intensity profile imparted by the filter onto the pulse is reasonably well preserved after the amplification stage, where more energetic pulses can be extracted from the cavity.

The pulse evolution is illustrated by plots of the root-mean-square (rms) pulse duration and spectral bandwidth as functions of position in the cavity, and quantified with the metric 4 (Fig. 3). Here, ψ is the pulse being evaluated and χ is a specific shape fit with the same energy and FWHM duration. The evolution shown for the triangular pulse-shaping regime is representative of those observed for the other shaping regimes too, in which the typical pulse parameters evolve in a closely similar fashion along the cavity, though small quantitative differences may exist. It is seen that during the short amplification stage there is no strong reshaping (which confirms the results in Fig. 2), and that most of the nonlinear dynamics occur in the long passive fiber. The peak nonlinear phase shift ϕ N L = ∫ dz γ(z)P 0 (z) (P 0 is the pulse peak power) that the pulse accumulates in one cycle around the cavity is slightly greater than 9 rad, with ϕ N L being slightly greater than 1 rad in the amplifier fiber and ϕ N L ∼ 8 rad in the passive fiber. This indicates that the laser relies on rather strong nonlinearity combined with spectral filtering to stabilize the pulse in the cavity. The nonlinear evolution in the passive fiber is monotonic with the growth of both temporal and spectral widths. The filter compensates for both temporal and spectral broadening, and cancels the large temporal phase ac-cumulation in the fiber. The spectral breathing factor, defined as the ratio of the spectral FWHM at the input and the output of the filter, is approximately 6 in the example of Fig. 3. The principle of filtering a pulse both in frequency and time due to the large chirp present has already been exploited to achieve new mode-locking regimes in fiber lasers [3,4]. In the present work we extend this approach to more complex features. Because the nonlinearly broadened spectrum of the pulse at the output of the passive fiber is significantly wider than the filter's spectral response and fairly flat within the filter bandwidth (Fig. 2), it can be sliced without caring for the details of its structure. This is the enabling mechanism for the formation of pulses of any desired temporal shape at the output of the filter, determined by the filter's transfer function [15]. It is worth noting here that steady-state pulse shaping in an oscillator requires the generated pulse to fulfill the constraints imposed by the cavity, and formation of a self-consistent solution in the cavity is in general a non-trivial problem. Despite substantial research in this field, qualitatively new phenomena are still being discovered. To gain a broader understanding of the laser dynamics, we investigated the effect of net dispersion on the laser response. Figure 4 shows results obtained for a triangular waveform function applied to the filter. It is seen that the best triangular pulses after spectral filtering are obtained for small values of normal net dispersion (∼ 0.005 ps 2 ) and are close to transform-limited pulses. In the cases of bright parabolic and flat-top shaping functions (not shown in Fig. 4) we observed a shift of the dispersion range where the best parabolic and flat-top pulses can be generated towards small net anomalous values (∼ -0.01 ps 2 ) and slightly larger normal values (∼ 0.02 ps 2 ), respectively. Note that the net dispersion is controlled by adjusting the transfer function of the pulse shaper; therefore, no physical change in the cavity is required in order to change the output from one pulse shape to another, provided that a programmable pulse shaper is used. The time-bandwidth product of the pulse remains very close to the transform-limit for a triangular pulse (0.54) in the dispersion region being considered, which reveals that the potential of tuning the output pulse temporal duration through in-cavity linear chirping is minimal. This stems from the filtering process that is used, i.e., slicing of a much broader spectrum, and indicates that one should act directly on the waveform function of the filter to control the output pulse width. This result is not surprising in fact, as a triangular, parabolic or flat-top temporal profile is rather sensitive to group delay. In conclusion, we have numerically shown the operation of a passively mode-locked fiber laser in different pulse-shaping regimes, including bright and dark parabolic, flat-top, triangular and saw-tooth waveform generations, depending on the amplitude profile of an in-cavity spectral filter. Using a spectral filter based on a programmable optical processor, one would be able to easily reconfigure the operation of the laser with a computer interface. From a practical viewpoint, the linear pulse shaping approach used here is attractive because it provides a high degree of control over the output pulse shape of the laser to adjust its operation to different experimental requirements. Our work confirms the great potential of the concept of an in-cavity pulse shaper for controlling the dynamics and the output of mode-locked fiber lasers. Further, our results are of particular relevance with the high interest in the generation of specialized pulse waveforms for applications in optical signal processing and manipulation.

M 2 = ∫ dt ( |ψ| 2 -|χ| 2 ) 2 / ∫ dt |ψ|

Fig. 1 .

 1 Fig. 1. Schematic of the laser. YDF: ytterbium-doped fiber; NDF: normally dispersive fiber; SA: saturable absorber.

  1 ps; a flat-top pulse shaper where h(t) = θ (τ -|t|) with τ = 0.75 ps; a triangular pulse shaper where h(t) = √ 1 -|t/τ |θ (τ -|t|) with τ = 1 ps; and a sawtooth pulse shaper where we define h

Fig. 2 .

 2 Fig. 2. (Color online) Temporal intensity and chirp profiles (left) and spectral intensity profile (right) of the pulse after the pulse shaper (blue solid) for a (a) bright parabolic, (b) dark parabolic, (c) flat-top, (d) triangularand (e) saw-tooth shaping function. Also shown are the target temporal and spectral profiles (dashed red), the temporal profiles at the exit of the gain fiber (green), and the spectral profiles before the pulse shaper (black).

Fig. 3 .

 3 Fig. 3. (Color online) Top: Evolution of the rms temporal (red circles) and spectral (blue triangles) widths of the pulse along the cavity for the triangular pulse-shaping regime. Bottom: Evolution of the misfit parameter to a triangular temporal shape (black rhombs).

Fig. 4 .

 4 Fig. 4. (Color online) Misfit parameter to a triangular temporal shape (blue squares) and time-bandwidth product (red circles) at the output of the pulse shaper versus net cavity dispersion.

The authors would like to acknowledge support by the Leverhulme Trust (grant RPG-278). They also thank Dr. Miguel Preciado and Dr. Mykhaylo Dubov for useful discussions.