text: DYNAMICAL SIMPLICES AND FRAI¨SSE´ THEORY 7 states that any isomorphism between ﬁnite Boolean subalgebras extends to an au- tomorphism of the whole structure, that is, this structure is homogeneous. Thus, its age is a Fra¨ısse´ class. We are now concerned with the other direction: building dynamical simplices from Fra¨ısse´ classes of E-structures. We will use the fact that the clopen algebra Clopen(X) of a Cantor space X is the unique (up to isomorphism) atomless count- able Boolean algebra; and that the set of ﬁnitely additive probability measures on Clopen(X) is naturally identiﬁed with the compact space P(X) of Borel probabil- ity measures on X. K B From now on, we only consider Fra¨ısse´ subclasses of which satisfy the ∈ K E → ∈ nontriviality condition that, given any A , there is an embedding α: A B K ∈ such that for all atoms a A α(a) is not an atom of B. We call such classes suitable. K B Given any suitable Fra¨ısse´ subclass of , the underlying Boolean algebra of K E the limit of is a countable atomless Boolean algebra, which we see as the algebra ∈ of clopen sets of a Cantor space XK by Stone duality; then for any e E we see the K measur{e µe}as a probability measure on XK. We denote by S( ) the closed convex hull of µe e∈E inside P(XK). K K Proposition 3.9. Let be a Fra¨ısse´ class of E-structures. Then S( ) is a dynamical simplex if and only if the following conditions are satisﬁed: ∈ K ∈ (1) For any A ∈(cid:87)K, and an∈y nonzero a A, infe µe(a) > 0.∈ K (cid:48) ∈ (2) For any A , any a(cid:48) A and≤any ε > 0, there exist∈s B and a(cid:48)1, . . . , an, a B suc∈h that ai = a , µe(ai) ε for all i and all e E, and µe(a ) = µe(a) for all e E. ∈ K ∈ ∈ ≤ − ∈ (3) For any A, B and any a ∈AK, b B,(cid:48)if µ(cid:48) e∈(a) µe(b) (cid:48)ε for all e E and(cid:48) some ε > 0 then there exists C and a , b C such that a is contained in b (cid:48) (cid:48) ∈ and µe(a) = µe(a ), µe(b) = µe(b ) for all e E. K Implicit in the above Proposition is that, under its assumptions, is automat- ically suitable: suitability directly follows from the combination of conditions (1) and (2), and the amalgamation property of a Fra¨ısse´ class. Proof. The fact that (1) and (2) are necessary is well-known and easily checked (see for instance Proposition 2.5 of [IM]); (3) directly follows from the Glasner–Weiss property. Conversely, assume that all three conditions above are satisﬁed. It is clear that K (3) (and homogeneity of a Fra¨ısse´ limit) implies that S( ) satisﬁes the Glasner– ∈ K Weiss property. Now ﬁx ν S( ). To see that ν has full support, pick some ≥ nonempt∈y clopen U in XK; the≥n by (1) there exists ε > 0 such that µe(U) ε for all e E, hence also ν(U) ε. Finally, the combination of (2) and (3) (and ⊂ homogeneity) implies that, given any clopen U XK and any ε > 0 there exists ≤ ∈ a covering of U b≤y clopens U1, . . . , Un such that µe(Ui) ε for all i and all e E(cid:3), hence also ν(Ui) ε for all i, and this in turn implies that ν is atomless. 4. A FRA¨ISSE´ THEORETIC PROOF OF DOWNAROWICZ’S THEOREM

text: DYNAMICAL

text: SIMPLICES

text: AND

text: FRAI¨SSE´

text: THEORY

text: states

text: that

text: any

text: isomorphism

text: between

text: ﬁnite

text: Boolean

text: subalgebras

text: extends

text: to

text: an

text: au-

text: tomorphism

text: of

text: the

text: whole

text: structure,

text: that

text: is,

text: this

text: structure

text: is

text: homogeneous.

text: Thus,

text: its

text: age

text: is

text: a

text: Fra¨ısse´

text: class.

text: We

text: are

text: now

text: concerned

text: with

text: the

text: other

text: direction:

text: building

text: dynamical

text: simplices

text: from

text: Fra¨ısse´

text: classes

text: of

text: E-structures.

text: We

text: will

text: use

text: the

text: fact

text: that

text: the

text: clopen

text: algebra

text: Clopen(X)

text: of

text: a

text: Cantor

text: space

text: X

text: is

text: the

text: unique

text: (up

text: to

text: isomorphism)

text: atomless

text: count-

text: able

text: Boolean

text: algebra;

text: and

text: that

text: the

text: set

text: of

text: ﬁnitely

text: additive

text: probability

text: measures

text: on

text: Clopen(X)

text: is

text: naturally

text: identiﬁed

text: with

text: the

text: compact

text: space

text: P(X)

text: of

text: Borel

text: probabil-

text: ity

text: measures

text: on

text: X.

text: K

text: B

text: From

text: now

text: on,

text: we

text: only

text: consider

text: Fra¨ısse´

text: subclasses

text: of

text: which

text: satisfy

text: the

text: K

text: E

text: nontriviality

text: condition

text: that,

text: given

text: any

text: A

text: there

text: is

text: an

text: embedding

text: α:

text: A

text: B

text: K

text: such

text: that

text: for

text: all

text: atoms

text: a

text: A

text: α(a)

text: is

text: not

text: an

text: atom

text: of

text: B.

text: We

text: call

text: such

text: classes

text: suitable.

text: K

text: B

text: Given

text: any

text: suitable

text: Fra¨ısse´

text: subclass

text: of

text: the

text: underlying

text: Boolean

text: algebra

text: of

text: K

text: E

text: the

text: limit

text: of

text: is

text: a

text: countable

text: atomless

text: Boolean

text: algebra,

text: which

text: we

text: see

text: as

text: the

text: algebra

text: of

text: clopen

text: sets

text: of

text: a

text: Cantor

text: space

text: XK

text: by

text: Stone

text: duality;

text: then

text: for

text: any

text: e

text: E

text: we

text: see

text: the

text: K

text: measur{e

text: µe}as

text: a

text: probability

text: measure

text: on

text: XK.

text: We

text: denote

text: by

text: S(

text: the

text: closed

text: convex

text: hull

text: of

text: µe

text: e∈E

text: inside

text: P(XK).

text: K

text: K

text: Proposition

text: Let

text: be

text: a

text: Fra¨ısse´

text: class

text: of

text: E-structures.

text: Then

text: S(

text: is

text: a

text: dynamical

text: simplex

text: if

text: and

text: only

text: if

text: the

text: following

text: conditions

text: are

text: satisﬁed:

text: K

text: For

text: any

text: A

text: and

text: an∈y

text: nonzero

text: a

text: A,

text: infe

text: µe(a)

text: K

text: For

text: any

text: A

text: any

text: A

text: and≤any

text: ε

text: there

text: exist∈s

text: B

text: and

text: an,

text: a

text: B

text: suc∈h

text: that

text: ai

text: a

text: µe(ai)

text: ε

text: for

text: all

text: i

text: and

text: all

text: e

text: E,

text: and

text: µe(a

text: µe(a)

text: for

text: all

text: e

text: E.

text: K

text: For

text: any

text: A,

text: B

text: and

text: any

text: a

text: ∈AK,

text: b

text: e∈(a)

text: µe(b)

text: for

text: all

text: e

text: E

text: some

text: ε

text: then

text: there

text: exists

text: C

text: and

text: a

text: b

text: C

text: such

text: that

text: a

text: is

text: contained

text: in

text: b

text: and

text: µe(a)

text: µe(a

text: µe(b)

text: µe(b

text: for

text: all

text: e

text: E.

text: K

text: Implicit

text: in

text: the

text: above

text: Proposition

text: is

text: that,

text: under

text: its

text: assumptions,

text: is

text: automat-

text: ically

text: suitable:

text: suitability

text: directly

text: follows

text: from

text: the

text: combination

text: of

text: conditions

text: and

text: and

text: the

text: amalgamation

text: property

text: of

text: a

text: Fra¨ısse´

text: class.

text: Proof.

text: The

text: fact

text: that

text: and

text: are

text: necessary

text: is

text: well-known

text: and

text: easily

text: checked

text: (see

text: for

text: instance

text: Proposition

text: of

text: [IM]);

text: directly

text: follows

text: from

text: the

text: Glasner–Weiss

text: property.

text: Conversely,

text: assume

text: that

text: all

text: three

text: conditions

text: above

text: are

text: satisﬁed.

text: It

text: is

text: clear

text: that

text: K

text: (and

text: homogeneity

text: of

text: a

text: Fra¨ısse´

text: limit)

text: implies

text: that

text: S(

text: satisﬁes

text: the

text: Glasner–

text: K

text: Weiss

text: property.

text: Now

text: ﬁx

text: ν

text: S(

text: To

text: see

text: that

text: ν

text: has

text: full

text: support,

text: pick

text: some

text: nonempt∈y

text: clopen

text: U

text: in

text: XK;

text: the≥n

text: by

text: there

text: exists

text: ε

text: such

text: that

text: µe(U)

text: ε

text: for

text: all

text: e

text: E,

text: hence

text: also

text: ν(U)

text: ε.

text: Finally,

text: the

text: combination

text: of

text: and

text: (and

text: homogeneity)

text: implies

text: that,

text: given

text: any

text: clopen

text: U

text: XK

text: and

text: any

text: ε

text: there

text: exists

text: a

text: covering

text: of

text: U

text: b≤y

text: clopens

text: Un

text: such

text: that

text: µe(Ui)

text: ε

text: for

text: all

text: i

text: and

text: all

text: e

text: hence

text: also

text: ν(Ui)

text: ε

text: for

text: all

text: i,

text: and

text: this

text: in

text: turn

text: implies

text: that

text: ν

text: is

text: atomless.

text: A

text: FRA¨ISSE´

text: THEORETIC

text: PROOF

text: OF

text: DOWNAROWICZ’S

text: THEOREM


text: ∈ − E − E from (18) for χ Vhr to b(cid:88)e ch(cid:90)osen precisely below, setting v(cid:90):= u (uh) (χ) for brevity. Integration by parts and re-ordering of the terms yields √ (cid:107) ∇ − E (cid:107) (cid:90) ∇ · ∇E − ∇E A (u (u )) 2 = (f + ΠA (u )) v dx [ΠA (u )]v ds + s (u , χ) h Ω h h h h T∈T T Γint − ∇E · ∇ + (A ΠA) (u ) v dx. h Ω Application of Cauchy-Schwarz ine(cid:16)qu(cid:88)ality r(cid:17)esu(cid:0)lts in (cid:1) √ (cid:107) ∇ − E (cid:107) ≤ 1 (cid:107) − (cid:107) (cid:107) − (cid:107) 1 A (u (u )) 2 η2 2 h 1v 2 + h 1/2v 2 2 + s (u , χ) h Ω ∈T T Ω Γint h h (31) T (cid:107) − ∇E (cid:107) (cid:107)∇ (cid:107) + (A ΠA) (u ) v . h Ω Ω − E → Selecting χ = Π (u (u )), (with Π : L2(Ω) V r the orthogonal L2-projection operator r h r h onto V r,) we have h (cid:107) − (cid:107) ≤ (cid:107) − − E − (cid:107) (cid:107) − − E (cid:107) h 1v h 1(u (u ) χ) + h 1(χ (χ)) Ω h Ω Ω ≤ (cid:107)∇ − E (cid:107) (cid:107) − − E (cid:107) C (u (u )) + h 1(χ (χ)) . h Ω Ω Now, we have the bound (cid:0) (cid:88) (cid:1) (cid:107) − − E (cid:107) ≤ (cid:107) − (cid:107) (cid:107) − − E − (cid:107) h 1(χ (χ)) 2 C h 1/2[χ] 2 = C h 1/2[u (u ) χ] 2 Ω KP,0 Γ KP,0 h Γ ≤ (cid:107) − − E − (cid:107) (cid:107)∇ − E − (cid:107) C h 1(u (u ) χ) 2 + (u (u ) χ) 2 h Ω h T ∈T T ≤ (cid:107)∇ − E (cid:107) C (u (u )) 2 , h Ω from the best approximation properties of the L2-projection and its stability in the local H1- seminorm. Completely analogously, we can show also that (cid:107) − (cid:107) ≤ (cid:107) − − E − (cid:107) (cid:107) − − E (cid:107) h 1/2v h 1/2(u (u ) χ) + h 1/2(χ (χ)) Γint h Γint Γint ≤ (cid:107)∇ − E (cid:107) (cid:107) − − E (cid:107) C (u (u )) + h 1/2(χ (χ)) . h Ω Γint and the bound (cid:107) − − E (cid:107) ≤ (cid:107)∇ − E (cid:107) h 1/2(χ (χ)) 2 C (u (u )) 2 . Γint h Ω Next, using a similar line of argument, we also have (cid:107)∇ (cid:107) ≤ (cid:107)∇ − E (cid:107) v C (u (u )) 2 . Ω h Ω (cid:88) (cid:88) (cid:0) (cid:1) (cid:0) (cid:1) Moreover, Assumptions 2.4, 2.3 and Re(cid:101)mark 2.5 imply ≤ − s (u , χ) = s (cid:16)(u(cid:88), χ) C h2(cid:17)αs (cid:16)((cid:88)u , u ) 1/2 h 2αs (χ,(cid:17)χ) 1/2 h h (cid:101) h,T h 0 T h,T h h T h,T ∈T ∈T T T (32) ≤ 1/2 − (cid:107) − (cid:107) 1/2 C C1/2 h2αs (u , u ) h 2α hα 1/2[χ] 2 , 0 0 T h,T h h T ∂T ∈T ∈T (cid:88) T (cid:88) T (cid:88) and we also have − (cid:107) − (cid:107) ≤ (cid:107) − (cid:107) (cid:107) − − E − (cid:107) h 2α hα 1/2[χ] 2 C h 1/2[χ] 2 = C h 1/2[u (u ) χ] 2 T ∂T ∂T h ∂T ∈T ∈T ∈T T T T ≤ (cid:107)∇ − E (cid:107) C (u (u )) 2 . h Ω Combining the above estimates and applying them to estimate the respective terms on the right-hand side of (31), we arrive at the a posteriori bound. 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: E

text: E

text: from

text: for

text: χ

text: Vhr

text: to

text: precisely

text: below,

text: setting

text: u

text: (uh)

text: (χ)

text: for

text: brevity.

text: Integration

text: by

text: parts

text: and

text: re-ordering

text: of

text: the

text: terms

text: yields

text: E

text: ∇E

text: ∇E

text: A

text: (u

text: (u

text: (f

text: ΠA

text: (u

text: v

text: dx

text: [ΠA

text: (u

text: )]v

text: ds

text: s

text: (u

text: χ)

text: h

text: Ω

text: h

text: h

text: h

text: h

text: T∈T

text: T

text: Γint

text: ∇E

text: (A

text: ΠA)

text: (u

text: v

text: dx.

text: h

text: Ω

text: Application

text: of

text: Cauchy-Schwarz

label: equation

text: in

text: E

text: A

text: (u

text: (u

text: η2

text: h

text: h

text: s

text: (u

text: χ)

text: h

text: Ω

text: ∈T

text: T

text: Ω

text: Γint

text: h

text: h

text: T

text: ∇E

text: (A

text: ΠA)

text: (u

text: v

text: h

text: Ω

text: Ω

text: E

text: Selecting

text: χ

text: Π

text: (u

text: (u

text: (with

text: Π

text: V

text: r

text: the

text: orthogonal

text: operator

text: r

text: h

text: r

text: h

text: onto

text: V

text: r,)

text: we

text: have

text: h

text: E

text: E

text: h

text: h

text: (u

text: χ)

text: h

text: (χ))

text: Ω

text: h

text: Ω

text: Ω

text: E

text: E

text: C

text: (u

text: (u

text: h

text: (χ))

text: h

text: Ω

text: Ω

text: Now,

text: we

text: have

text: the

text: bound

text: E

text: E

text: h

text: (χ))

text: C

text: h

text: C

text: h

text: (u

text: χ]

text: Ω

text: Γ

text: h

text: Γ

text: E

text: E

text: C

text: h

text: (u

text: χ)

text: (u

text: (u

text: χ)

text: h

text: Ω

text: h

text: T

text: ∈T

text: T

text: E

text: C

text: (u

text: (u

text: h

text: Ω

text: from

text: the

text: best

text: approximation

text: properties

text: of

text: the

text: and

text: its

text: stability

text: in

text: the

text: local

text: seminorm.

text: Completely

text: analogously,

text: we

text: can

text: show

text: also

text: that

text: E

text: E

text: h

text: h

text: (u

text: χ)

text: h

text: (χ))

text: Γint

text: h

text: Γint

text: Γint

text: E

text: E

text: C

text: (u

text: (u

text: h

text: (χ))

text: h

text: Ω

text: Γint

text: and

text: the

text: bound

text: E

text: E

text: h

text: (χ))

text: C

text: (u

text: (u

text: Γint

text: h

text: Ω

text: Next,

text: using

text: a

text: similar

text: line

text: of

text: argument,

text: we

text: also

text: have

text: E

text: v

text: C

text: (u

text: (u

text: Ω

text: h

text: Ω

text: Moreover,

text: Assumptions

text: and

text: imply

text: s

text: (u

text: χ)

text: s

text: χ)

text: C

text: u

text: h

text: h

text: h

text: h,T

text: h

text: T

text: h,T

text: h

text: h

text: T

text: h,T

text: ∈T

text: ∈T

text: T

text: T

text: C

text: (u

text: u

text: h

text: 2α

text: hα

text: T

text: h,T

text: h

text: h

text: T

text: ∂T

text: ∈T

text: ∈T

text: T

text: T

text: and

text: we

text: also

text: have

text: E

text: h

text: 2α

text: hα

text: C

text: h

text: C

text: h

text: (u

text: χ]

text: T

text: ∂T

text: ∂T

text: h

text: ∂T

text: ∈T

text: ∈T

text: ∈T

text: T

text: T

text: T

text: E

text: C

text: (u

text: (u

text: h

text: Ω

text: Combining

text: the

text: above

text: estimates

text: and

text: applying

text: them

text: to

text: estimate

text: the

text: respective

text: terms

text: on

text: the

text: right-hand

text: side

text: of

text: we

text: arrive

text: at

text: the

text: a

text: posteriori

text: bound.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: FEM for general polygonal/polyhedral element shapes. Also, recalling that R-FEM is based on discontinuous approximation spaces also, R-FEM is expected to be able to produce stable conforming approximations in the context of convection-dominated problems. A numerical investigation in this direction is presented in the numerical experiments below. The idea of variational methods involving some form of recovery, e.g., as (enhanced) gradient approximation, has appeared in various forms in the literature, especially in the context of dG methods, see, e.g., [18, 14, 8, 16]. All these approaches, however, recover the gradient of the numerical solution, through the solution of additional local (or global) weak problems. At the other end of the spectrum, the recent framework of virtual element methods (VEMs) [5] applied to meshes with polygonal/polyhedral element shapes, use non-polynomial basis functions to ensure conformity, which are not computed fully in practice. Indeed, the local VEM spaces are constructed so that they contain a, typically discontinuous, polynomial subspace ensuring optimal approximation; the approximate solution is then computed over this subspace and over the mesh skeleton. As a ﬁrst work introducing the recovered ﬁnite element method, we conﬁne ourselves to its deﬁnition for linear elliptic problems on simplicial and/or box-type triangulations (Section ). After discussing its relation on known, popular methods (Section ), we prove a priori bounds (Section ) showing the optimality of the proposed method with respect to meshsize h, as well as residual-type a posteriori error bounds (Section ). We also investigate carefully the lowest order case, whereby the underlying discontinuous space V consists of element-wise constant functions h recovered into conforming linear elements on a triangular mesh; the resulting method is shown to converge optimally in the energy norm. We investigate a number of implementation and conditioning issues for the proposed method, assessing its competitiveness against FEM and dG in terms of complexity (Section ). Numerical experiments highlighting the good approximation properties of the method in practice and comparisons against FEM and dG are performed in Section . Finally, we conclude by discussing a number of currently developed and future extensions of the R-FEM framework to complex problems. ≤ ≤ ∞ Throughout this work we denote the standard Lebesgue spaces by Lp(ω), 1 p , ⊂ R (cid:107) · (cid:107) ω d, d = 2, 3, with corresponding norms ; the norm of L2(ω) will be denoted by (cid:107)·(cid:107) Lp(ω) ∈ R for brevity. Let also Hs(ω), be the Hilbertian Sobolev space of index s of real-valued ω ⊂ R functions deﬁned on ω d, constructed via standard interpolation and/or duality procedures, (cid:107)·(cid:107) |·| along with the corresponding norm and seminorm and , respectively. We also denote s,ω s,ω by H1(ω) the space of functions in H1(ω) with vanishing trace on ∂ω. 0 R For Ω a bounded open polygonal domain in d, d = 2, 3, with ∂Ω denoting its boundary, we consider the elliptic problem −∇ · ∇ A u = f in Ω, (1) ∈ − ∈ ∞ × where f H 1(Ω), for some uniformly positive deﬁnite diﬀusion tensor A [L (Ω)]d d. For simplicity of the presentation only, we impose homogeneous essential boundary conditions u = 0 on ∂Ω, although this is by no means an essential restriction on what follows. Moreover, we shall also brieﬂy consider a linear convection-diﬀusion problem in Section to highlight the versatility of the proposed framework. 2 Recovered ﬁnite element method T Let be a regular subdivision of Ω into disjoint simplicial or box-type (quadrilateral/hexahedral) ∈ T T elements T . We assume that the subdivision is shape-regular (see, e.g., p.124 in [12]), ∪ that Ω¯ = ∈T T¯ and that the elemental faces are straight line (for d = 2) or planar (for d = 3) T segments; these will be, henceforth, referred to as facets. By Γ we shall denote the union of all 3

text: FEM

text: for

text: general

text: polygonal/polyhedral

text: element

text: shapes.

text: Also,

text: recalling

text: that

text: R-FEM

text: is

text: based

text: on

text: discontinuous

text: approximation

text: spaces

text: also,

text: R-FEM

text: is

text: expected

text: to

text: be

text: able

text: to

text: produce

text: stable

text: conforming

text: approximations

text: in

text: the

text: context

text: of

text: convection-dominated

text: problems.

text: A

text: numerical

text: investigation

text: in

text: this

text: direction

text: is

text: presented

text: in

text: the

text: numerical

text: experiments

text: below.

text: The

text: idea

text: of

text: variational

text: methods

text: involving

text: some

text: form

text: of

text: recovery,

text: e.g.,

text: as

text: (enhanced)

text: gradient

text: approximation,

text: has

text: appeared

text: in

text: various

text: forms

text: in

text: the

text: literature,

text: especially

text: in

text: the

text: context

text: of

text: dG

text: methods,

text: see,

text: e.g.,

text: All

text: these

text: approaches,

text: however,

text: recover

text: the

text: gradient

text: of

text: the

text: numerical

text: solution,

text: through

text: the

text: solution

text: of

text: additional

text: local

text: (or

text: global)

text: weak

text: problems.

text: At

text: the

text: other

text: end

text: of

text: the

text: spectrum,

text: the

text: recent

text: framework

text: of

text: virtual

text: element

text: methods

text: (VEMs)

text: applied

text: to

text: meshes

text: with

text: polygonal/polyhedral

text: element

text: shapes,

text: use

text: non-polynomial

text: basis

text: functions

text: to

text: ensure

text: conformity,

text: which

text: are

text: not

text: computed

text: fully

text: in

text: practice.

text: Indeed,

text: the

text: local

text: VEM

text: spaces

text: are

text: constructed

text: so

text: that

text: they

text: contain

text: a,

text: typically

text: discontinuous,

text: polynomial

text: subspace

text: ensuring

text: optimal

text: approximation;

text: the

text: approximate

text: solution

text: is

text: then

text: computed

text: over

text: this

text: subspace

text: and

text: over

text: the

text: mesh

text: skeleton.

text: As

text: a

text: ﬁrst

text: work

text: introducing

text: the

text: recovered

text: ﬁnite

text: element

text: method,

text: we

text: conﬁne

text: ourselves

text: to

text: its

text: deﬁnition

text: for

text: linear

text: elliptic

text: problems

text: on

text: simplicial

text: and/or

text: box-type

text: triangulations

text: (Section

text: After

text: discussing

text: its

text: relation

text: on

text: known,

text: popular

text: methods

text: (Section

text: we

text: prove

text: a

text: priori

text: bounds

text: (Section

text: showing

text: the

text: optimality

text: of

text: the

text: proposed

text: method

text: with

text: respect

text: to

text: meshsize

text: h,

text: as

text: well

text: as

text: residual-type

text: a

text: posteriori

text: error

text: bounds

text: (Section

text: We

text: also

text: investigate

text: carefully

text: the

text: lowest

text: order

text: case,

text: whereby

text: the

text: underlying

text: discontinuous

text: space

text: V

text: consists

text: of

text: element-wise

text: constant

text: functions

text: h

text: recovered

text: into

text: conforming

text: linear

text: elements

text: on

text: a

text: triangular

text: mesh;

text: the

text: resulting

text: method

text: is

text: shown

text: to

text: converge

text: optimally

text: in

text: the

text: energy

text: norm.

text: We

text: investigate

text: a

text: number

text: of

text: implementation

text: and

text: conditioning

text: issues

text: for

text: the

text: proposed

text: method,

text: assessing

text: its

text: competitiveness

text: against

text: FEM

text: and

text: dG

text: in

text: terms

text: of

text: complexity

text: (Section

text: Numerical

text: experiments

text: highlighting

text: the

text: good

text: approximation

text: properties

text: of

text: the

text: method

text: in

text: practice

text: and

text: comparisons

text: against

text: FEM

text: and

text: dG

text: are

text: performed

text: in

text: Section

text: Finally,

text: we

text: conclude

text: by

text: discussing

text: a

text: number

text: of

text: currently

text: developed

text: and

text: future

text: extensions

text: of

text: the

text: R-FEM

text: framework

text: to

text: complex

text: problems.

text: Throughout

text: this

text: work

text: we

text: denote

text: the

text: standard

text: Lebesgue

text: spaces

text: by

text: Lp(ω),

text: p

text: R

text: ω

text: d,

text: d

text: with

text: corresponding

text: norms

text: the

text: norm

text: of

text: will

text: be

text: denoted

text: by

text: Lp(ω)

text: R

text: for

text: brevity.

text: Let

text: also

text: Hs(ω),

text: be

text: the

text: Hilbertian

text: Sobolev

text: space

text: of

text: index

text: s

text: of

text: real-valued

text: ω

text: R

text: functions

text: deﬁned

text: on

text: ω

text: d,

text: constructed

text: via

text: standard

text: interpolation

text: and/or

text: duality

text: procedures,

text: along

text: with

text: the

text: corresponding

text: norm

text: and

text: seminorm

text: and

text: respectively.

text: We

text: also

text: denote

text: s,ω

text: s,ω

text: by

text: the

text: space

text: of

text: functions

text: in

text: with

text: vanishing

text: trace

text: on

text: ∂ω.

text: R

text: For

text: Ω

text: a

text: bounded

text: open

text: polygonal

text: domain

text: in

text: d,

text: d

text: with

text: ∂Ω

text: denoting

text: its

text: boundary,

text: we

text: consider

text: the

text: elliptic

text: problem

text: A

text: u

text: f

text: in

text: Ω,

text: where

text: f

text: H

text: for

text: some

text: uniformly

text: positive

text: deﬁnite

text: diﬀusion

text: tensor

text: A

text: [L

text: (Ω)]d

text: d.

text: For

text: simplicity

text: of

text: the

text: presentation

text: only,

text: we

text: impose

text: homogeneous

text: essential

text: boundary

text: conditions

text: u

text: on

text: ∂Ω,

text: although

text: this

text: is

text: by

text: no

text: means

text: an

text: essential

text: restriction

text: on

text: what

text: follows.

text: Moreover,

text: we

text: shall

text: also

text: brieﬂy

text: consider

text: a

text: linear

text: convection-diﬀusion

text: problem

text: in

text: Section

text: to

text: highlight

text: the

text: versatility

text: of

text: the

text: proposed

text: framework.

text: Recovered

text: ﬁnite

text: element

text: method

text: T

text: Let

text: be

text: a

text: regular

text: subdivision

text: of

text: Ω

text: into

text: disjoint

text: simplicial

text: or

text: box-type

text: (quadrilateral/hexahedral)

text: T

text: T

text: elements

text: T

text: We

text: assume

text: that

text: the

text: subdivision

text: is

text: shape-regular

text: (see,

text: e.g.,

text: in

text: that

text: Ω¯

text: ∈T

text: T¯

text: and

text: that

text: the

text: elemental

text: faces

text: are

text: straight

text: line

text: (for

text: d

text: or

text: planar

text: (for

text: d

text: T

text: segments;

text: these

text: will

text: be,

text: henceforth,

text: referred

text: to

text: as

text: facets.

text: By

text: Γ

text: we

text: shall

text: denote

text: the

text: union

text: of

text: all


text: [2] D. N. Arnold, F. Brezzi, B. Cockburn, and L. D. Marini, Uniﬁed analysis of dis- continuous Galerkin methods for elliptic problems, SIAM J. Numer. Anal., 39 (2001/02), pp. 1749–1779. [3] R. E. Bank and L. R. Scott, On the conditioning of ﬁnite element equations with highly reﬁned meshes, SIAM J. Numer. Anal., 26 (1989), pp. 1383–1394. [4] G. R. Barrenechea, E. H. Georgoulis, and T. Pryer, Recovered mixed ﬁnite element methods, in preparation. [5] L. Beira˜o da Veiga, F. Brezzi, A. Cangiani, G. Manzini, L. D. Marini, and A. Russo, Basic principles of virtual element methods, Math. Models Methods Appl. Sci., 23 (2013), pp. 199–214. [6] S. C. Brenner and L.-Y. Sung, Linear ﬁnite element methods for planar linear elastic- ity, Math. Comp., 59 (1992), pp. 321–338. [7] , C0 interior penalty methods for fourth order elliptic boundary value problems on polygonal domains, J. Sci. Comput., 22/23 (2005), pp. 83–118. [8] A. Buffa and C. Ortner, Compact embeddings of broken Sobolev spaces and applica- tions, IMA J. Numer. Anal., 29 (2009), pp. 827–855. [9] A. Cangiani, Z. Dong, and E. H. Georgoulis, hp-version space-time discontinuous Galerkin methods for parabolic problems on prismatic meshes, SIAM J. Sci. Comput., to appear. [10] A. Cangiani, Z. Dong, E. H. Georgoulis, and P. Houston, hp-version discontinuous Galerkin methods for advection-diﬀusion-reaction problems on polytopic meshes, ESAIM Math. Model. Numer. Anal., 50 (2016), pp. 699–725. [11] A. Cangiani, E. H. Georgoulis, and P. Houston, hp-version discontinuous Galerkin methods on polygonal and polyhedral meshes, Math. Models Methods Appl. Sci., 24 (2014), pp. 2009–2041. [12] P. G. Ciarlet, The ﬁnite element method for elliptic problems, vol. 40 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadel- phia, PA, 2002. Reprint of the 1978 original [North-Holland, Amsterdam; MR0520174 (58 #25001)]. [13] P. Cle´ment, Approximation by ﬁnite element functions using local regularization, RAIRO Analyse Num´erique, 9 (1975), pp. 77–84. [14] B. Cockburn, J. Gopalakrishnan, and R. Lazarov, Uniﬁed hybridization of dis- continuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems, SIAM J. Numer. Anal., 47 (2009), pp. 1319–1365. [15] B. Cockburn and C.-W. Shu, The Runge-Kutta local projection P 1-discontinuous- Galerkin ﬁnite element method for scalar conservation laws, RAIRO Mod´el. Math. Anal. Num´er., 25 (1991), pp. 337–361. [16] D. A. Di Pietro, A. Ern, and S. Lemaire, An arbitrary-order and compact-stencil dis- cretization of diﬀusion on general meshes based on local reconstruction operators, Comput. Methods Appl. Math., 14 (2014), pp. 461–472. 25 ##LTLine##

label: reference

text: D.

text: N.

text: Arnold,

text: F.

text: Brezzi,

text: B.

text: Cockburn,

text: and

text: L.

text: D.

text: Marini,

text: Uniﬁed

text: analysis

text: of

text: dis-

text: continuous

text: Galerkin

text: methods

text: for

text: elliptic

text: problems,

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: pp.

text: R.

text: E.

text: Bank

text: and

text: L.

text: R.

text: Scott,

text: On

text: the

text: conditioning

text: of

text: ﬁnite

text: element

text: equations

text: with

text: highly

text: reﬁned

text: meshes,

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: pp.

text: G.

text: R.

text: Barrenechea,

text: E.

text: H.

text: Georgoulis,

text: and

text: T.

text: Pryer,

text: Recovered

text: mixed

text: ﬁnite

text: element

text: methods,

text: in

text: preparation.

text: L.

text: Beira˜o

text: da

text: Veiga,

text: F.

text: Brezzi,

text: A.

text: Cangiani,

text: G.

text: Manzini,

text: L.

text: D.

text: Marini,

text: and

text: A.

text: Russo,

text: Basic

text: principles

text: of

text: virtual

text: element

text: methods,

text: Math.

text: Models

text: Methods

text: Appl.

text: Sci.,

text: pp.

text: S.

text: C.

text: Brenner

text: and

text: L.-Y.

text: Sung,

text: Linear

text: ﬁnite

text: element

text: methods

text: for

text: planar

text: linear

text: elastic-

text: ity,

text: Math.

text: Comp.,

text: pp.

text: interior

text: penalty

text: methods

text: for

text: fourth

text: order

text: elliptic

text: boundary

text: value

text: problems

text: on

text: polygonal

text: domains,

text: J.

text: Sci.

text: Comput.,

text: pp.

text: A.

text: Buffa

text: and

text: C.

text: Ortner,

text: Compact

text: embeddings

text: of

text: broken

text: Sobolev

text: spaces

text: and

text: applica-

text: tions,

text: IMA

text: J.

text: Numer.

text: Anal.,

text: pp.

text: A.

text: Cangiani,

text: Z.

text: Dong,

text: and

text: E.

text: H.

text: Georgoulis,

text: hp-version

text: space-time

text: discontinuous

text: Galerkin

text: methods

text: for

text: parabolic

text: problems

text: on

text: prismatic

text: meshes,

text: SIAM

text: J.

text: Sci.

text: Comput.,

text: to

text: appear.

text: A.

text: Cangiani,

text: Z.

text: Dong,

text: E.

text: H.

text: Georgoulis,

text: and

text: P.

text: Houston,

text: hp-version

text: discontinuous

text: Galerkin

text: methods

text: for

text: advection-diﬀusion-reaction

text: problems

text: on

text: polytopic

text: meshes,

text: ESAIM

text: Math.

text: Model.

text: Numer.

text: Anal.,

text: pp.

text: A.

text: Cangiani,

text: E.

text: H.

text: Georgoulis,

text: and

text: P.

text: Houston,

text: hp-version

text: discontinuous

text: Galerkin

text: methods

text: on

text: polygonal

text: and

text: polyhedral

text: meshes,

text: Math.

text: Models

text: Methods

text: Appl.

text: Sci.,

text: pp.

text: P.

text: G.

text: Ciarlet,

text: The

text: ﬁnite

text: element

text: method

text: for

text: elliptic

text: problems,

text: vol.

text: of

text: Classics

text: in

text: Applied

text: Mathematics,

text: Society

text: for

text: Industrial

text: and

text: Applied

text: Mathematics

text: (SIAM),

text: Philadel-

text: phia,

text: PA,

text: Reprint

text: of

text: the

text: original

text: [North-Holland,

text: Amsterdam;

text: P.

text: Cle´ment,

text: Approximation

text: by

text: ﬁnite

text: element

text: functions

text: using

text: local

text: regularization,

text: RAIRO

text: Analyse

text: Num´erique,

text: pp.

text: B.

text: Cockburn,

text: J.

text: Gopalakrishnan,

text: and

text: R.

text: Lazarov,

text: Uniﬁed

text: hybridization

text: of

text: dis-

text: continuous

text: Galerkin,

text: mixed,

text: and

text: continuous

text: Galerkin

text: methods

text: for

text: second

text: order

text: elliptic

text: problems,

text: SIAM

text: J.

text: Numer.

text: Anal.,

text: pp.

text: B.

text: Cockburn

text: and

text: C.-W.

text: Shu,

text: The

text: Runge-Kutta

text: local

text: projection

text: P

text: Galerkin

text: ﬁnite

text: element

text: method

text: for

text: scalar

text: conservation

text: laws,

text: RAIRO

text: Mod´el.

text: Math.

text: Anal.

text: Num´er.,

text: pp.

text: D.

text: A.

text: Di

text: Pietro,

text: A.

text: Ern,

text: and

text: S.

text: Lemaire,

text: An

text: arbitrary-order

text: and

text: compact-stencil

text: dis-

text: cretization

text: of

text: diﬀusion

text: on

text: general

text: meshes

text: based

text: on

text: local

text: reconstruction

text: operators,

text: Comput.

text: Methods

text: Appl.

text: Math.,

text: pp.

text: ##LTLine##


text: E ∩ If one can show, e.g., that (V 0) = V 1 H1(Ω), (at least for some appropriately designed h h 0 (cid:88) meshes,) then the ﬁrst term on the right-hand side of (25) becomes √ √ (cid:107) ∇ − E (cid:107) (cid:107) ∇ − (cid:107) ≤ | | inf A (u (v )) 2 = inf A (u w ) 2 C h2 u 2 , (26) ∈ h ∈ ∩ h T T,2 v V 0 w V 1 H1(Ω) ∈T h h h h 0 T from standard Bramble-Hilbert type approximation results [12], i.e., optimal linear conver- gence is retrieved. We shall now complete the proof of (26) for the case of a two-dimensional simplicial mesh. T E ∩ Lemma 4.3 For d = 2, let be a regular simplicial mesh. Then, we have (V 0) = V 1 H1(Ω). h h 0 N ∈ N Proof. Recalling that denotes the set of all Lagrange nodes ν Ω, we set to be the set 0 of respective Lagrange nodes situated on ∂Ω. (Since we are concerned with linear elements on N a simplicial mesh, is equal to the set of internal nodes in the mesh.) To prove the result, it is suﬃcient to prove that each Lagrange nodal basis φ can be constructed as a recovery of an ∈ E ν element-wise constant function ψ V 0, i.e., φ = (ψ ). ∈ ν N h ν ν N ⊂ N To construct ψ V 0, we split into a union of disjoint subsets as follows. Let ν h ∈ T 1 denote the set of nodes ν for which there exists a triangle T having ν as a node and the N1 N ⊂ N \ ∪ −1 N two remaining nodes in . For i = 2, . . . , r, for some r, let i 1 denote the set 0 ∈ T i j=1 j of nodes ν for which there exists a triangle T having ν as a node and the two remaining Ni ∈ N N ∪ i N nodes in − . The existence of an r such that = r follows from the assumption T i 1 j=1 j that is a regular simplicial mesh. {N } N Having constructed a pairwise disjoint subdivision r of , we can now give an algo- ∈ N j j=∈1 N − rithm for the construction of ψ . Let r be such that ν and set ψ = 1 = ( 1)0 on ∈ T ν ν rν N ν the element T with vertex ν and the two other vertices ν , ν in − . For each of the ν , rν ∈ T 1 2 rν 1 i there exists a triangle T i − , i = 1, 2, with one vertex being ν and the other two vertices N rν 1 i being in − . We now have 2 possibilities: 1) if T 1 − and T 2 − have a common vertex, say rν 2 ∈ T rν 1 rν 1 − ν , then there exists a triangle T − having vertices ν , ν and ν on which we set ψ = 1 3 rν 1 1 2 3 ν (notice that T − is necessarily diﬀerent to the T i − ’s); if T 1 − and T 2 − have no common rν 1 − − rν 1 rν 1 rν 1 vertex, we set ψ = 1 = ( 1)1 on both T 1 − , T 2 − . We continue the above algorithm by − ν rνI 1(cid:51) rν 1 N setting ψ = ( 1)j on T i − for an index set i, until we reach the boundary nodes in ν rν j j 0 for which the recovery imposes the homogeneous boundary conditions strongly. Noticing that − on each node ν there exist exactly two elements with non-zero values one +1 and the other 1, i E we conclude that φ = c (ψ ) for some c > 0, which already proves the result. ν ν (cid:3) Thus, we have proved the following a priori error bound. T Corollary 4.4 For d = 2, let be a regular and shape-regular simplicial mesh. Further, | ∈ ∈ T assuming that u H2(T ), T , and that α = 1 in Assumption 2.3, we have that (23) holds T with q = 1. So, we conclude that it is possible to have an optimally convergent ﬁnite element method for second order elliptic problems based on element-wise constant ﬁnite element spaces. This remarkable order increasing property of the method when recovering from element-wise con- stants to conforming linear elements appears to hold for greater values of r. In particular, we have observed numerically that A σ = c hs, (27) σ 10 ##LTLine## ##LTLine##

text: E

text: If

text: one

text: can

text: show,

text: e.g.,

text: that

text: (V

text: V

text: (at

text: least

text: for

text: some

text: appropriately

text: designed

text: h

text: h

text: meshes,)

text: then

text: the

text: ﬁrst

text: term

text: on

text: the

text: right-hand

text: side

text: of

text: becomes

text: E

text: inf

text: A

text: (u

text: (v

text: inf

text: A

text: (u

text: w

text: C

text: u

text: h

text: h

text: T

text: v

text: V

text: w

text: V

text: ∈T

text: h

text: h

text: h

text: h

text: T

text: from

text: standard

text: Bramble-Hilbert

text: type

text: approximation

text: results

text: i.e.,

text: optimal

text: linear

text: conver-

text: gence

text: is

text: retrieved.

text: We

text: shall

text: now

text: complete

text: the

text: proof

text: of

text: for

text: the

text: case

text: of

text: a

text: two-dimensional

text: simplicial

text: mesh.

text: T

text: E

text: Lemma

text: For

text: d

text: let

text: be

text: a

text: regular

text: simplicial

text: mesh.

text: Then,

text: we

text: have

text: (V

text: V

text: h

text: h

text: N

text: N

text: Proof.

text: Recalling

text: that

text: denotes

text: the

text: set

text: of

text: all

text: Lagrange

text: nodes

text: ν

text: Ω,

text: we

text: set

text: to

text: be

text: the

text: set

text: of

text: respective

text: Lagrange

text: nodes

text: situated

text: on

text: ∂Ω.

text: (Since

text: we

text: are

text: concerned

text: with

text: linear

text: elements

text: on

text: N

text: a

text: simplicial

text: mesh,

text: is

text: equal

text: to

text: the

text: set

text: of

text: internal

text: nodes

text: in

text: the

text: mesh.)

text: To

text: prove

text: the

text: result,

text: it

text: is

text: suﬃcient

text: to

text: prove

text: that

text: each

text: Lagrange

text: nodal

text: basis

text: φ

text: can

text: be

text: constructed

text: as

text: a

text: recovery

text: of

text: an

text: E

text: ν

text: element-wise

text: constant

text: function

text: ψ

text: V

text: i.e.,

text: φ

text: (ψ

text: ν

text: N

text: h

text: ν

text: ν

text: N

text: N

text: To

text: construct

text: ψ

text: V

text: we

text: split

text: into

text: a

text: union

text: of

text: disjoint

text: subsets

text: as

text: follows.

text: Let

text: ν

text: h

text: T

text: denote

text: the

text: set

text: of

text: nodes

text: ν

text: for

text: which

text: there

text: exists

text: a

text: triangle

text: T

text: having

text: ν

text: as

text: a

text: node

text: and

text: the

text: N

text: N

text: −1

text: N

text: two

text: remaining

text: nodes

text: in

text: For

text: i

text: r,

text: for

text: some

text: r,

text: let

text: i

text: denote

text: the

text: set

text: T

text: i

text: j

text: of

text: nodes

text: ν

text: for

text: which

text: there

text: exists

text: a

text: triangle

text: T

text: having

text: ν

text: as

text: a

text: node

text: and

text: the

text: two

text: remaining

text: Ni

text: N

text: N

text: i

text: N

text: nodes

text: in

text: The

text: existence

text: of

text: an

text: r

text: such

text: that

text: r

text: follows

text: from

text: the

text: assumption

text: T

text: i

text: j

text: that

text: is

text: a

text: regular

text: simplicial

text: mesh.

text: {N

text: N

text: Having

text: constructed

text: a

text: pairwise

text: disjoint

text: subdivision

text: r

text: of

text: we

text: can

text: now

text: give

text: an

text: algo-

text: N

text: j

text: N

text: rithm

text: for

text: the

text: construction

text: of

text: ψ

text: Let

text: r

text: be

text: such

text: that

text: ν

text: and

text: set

text: ψ

text: on

text: T

text: ν

text: ν

text: rν

text: N

text: ν

text: the

text: element

text: T

text: with

text: vertex

text: ν

text: and

text: the

text: two

text: other

text: vertices

text: ν

text: ν

text: in

text: For

text: each

text: of

text: the

text: ν

text: rν

text: T

text: rν

text: i

text: there

text: exists

text: a

text: triangle

text: T

text: i

text: i

text: with

text: one

text: vertex

text: being

text: ν

text: and

text: the

text: other

text: two

text: vertices

text: N

text: rν

text: i

text: being

text: in

text: We

text: now

text: have

text: possibilities:

text: if

text: T

text: and

text: T

text: have

text: a

text: common

text: vertex,

text: say

text: rν

text: T

text: rν

text: rν

text: ν

text: then

text: there

text: exists

text: a

text: triangle

text: T

text: having

text: vertices

text: ν

text: ν

text: and

text: ν

text: on

text: which

text: we

text: set

text: ψ

text: rν

text: ν

text: (notice

text: that

text: T

text: is

text: necessarily

text: diﬀerent

text: to

text: the

text: T

text: i

text: ’s);

text: if

text: T

text: and

text: T

text: have

text: no

text: common

text: rν

text: rν

text: rν

text: rν

text: vertex,

text: we

text: set

text: ψ

text: on

text: both

text: T

text: T

text: We

text: continue

text: the

text: above

text: algorithm

text: by

text: ν

text: rνI

text: rν

text: N

text: setting

text: ψ

text: on

text: T

text: i

text: for

text: an

text: index

text: set

text: i,

text: until

text: we

text: reach

text: the

text: boundary

text: nodes

text: in

text: ν

text: rν

text: j

text: j

text: for

text: which

text: the

text: recovery

text: imposes

text: the

text: homogeneous

text: boundary

text: conditions

text: strongly.

text: Noticing

text: that

text: on

text: each

text: node

text: ν

text: there

text: exist

text: exactly

text: two

text: elements

text: with

text: non-zero

text: values

text: one

text: and

text: the

text: other

text: i

text: E

text: we

text: conclude

text: that

text: φ

text: c

text: (ψ

text: for

text: some

text: c

text: which

text: already

text: proves

text: the

text: result.

text: ν

text: ν

text: Thus,

text: we

text: have

text: proved

text: the

text: following

text: a

text: priori

text: error

text: bound.

text: T

text: Corollary

text: For

text: d

text: let

text: be

text: a

text: regular

text: and

text: shape-regular

text: simplicial

text: mesh.

text: Further,

text: T

text: assuming

text: that

text: u

text: T

text: and

text: that

text: α

text: in

text: Assumption

text: we

text: have

text: that

text: holds

text: T

text: with

text: q

text: So,

text: we

text: conclude

text: that

text: it

text: is

text: possible

text: to

text: have

text: an

text: optimally

text: convergent

text: ﬁnite

text: element

text: method

text: for

text: second

text: order

text: elliptic

text: problems

text: based

text: on

text: element-wise

text: constant

text: ﬁnite

text: element

text: spaces.

text: This

text: remarkable

text: order

text: increasing

text: property

text: of

text: the

text: method

text: when

text: recovering

text: from

text: element-wise

text: con-

text: stants

text: to

text: conforming

text: linear

text: elements

text: appears

text: to

text: hold

text: for

text: greater

text: values

text: of

text: r.

text: In

text: particular,

text: we

text: have

text: observed

text: numerically

text: that

text: A

text: σ

text: c

text: hs,

text: σ

text: ##LTLine##

text: ##LTLine##


text: thus representing the stateless nature of HTTP. The web app’s model is thus a sequence of if statements deﬁning all the requests the web app can handle. Client communication A general HTTP request (and response) header comprises diﬀerent ﬁelds that are needed for the message to be processed by the browser. In our formalization, we don’t need to represent all the ﬁelds of a real request (or response) header as they are not relevant to the analysis, and thus we limit to: a variable representing the sender, a variable representing the receiver, and a concatenation of constants and variables representing the message. In case of a request, the message would be represented by the HTTP query string containing parameters and values. For example, a request to the URL http://example.com/index.php?page=menu.php can be represented as Client -> WebApp : index.Page, where index is a constant representing a web page and Page is a variable representing an HTTP query value. We proceed similarly to formalize a response from the web app to the client. We only represent the details needed for the analysis: – a constant representing the returned page (e.g., dashboard, admin etc), – the function file() when the web app performs a reading operation on the ﬁle-system, and – the function tuple() that, following [10], is returned only if the executed query is SELECT, UPDATE or DELETE. For example, the response WebApp -> Client : dashboard.file(fsi) can be used to represent the result of a successful request where the client receives the dashboard page. The message file(fsi) is returned to express that a ﬁle was retrieved from the ﬁle-system. § File-system and database communication As already stated in 1, whenever the web app has to read content from the ﬁle-system, it sends a readFile() request and whenever it has to write to the ﬁle-system, it sends a writeFile() request. When the web app has to perform a SQL query on the § database, it sends a query() request to the database (see 1). To allow the web app to represent sanitized input, we introduced an uninterpreted function sanitized() that allows the modeler to “switch on” or “switch oﬀ” the possi- bility of exploiting a vulnerability either of the ﬁle-system or of the database, letting the model-checker analyze the web app for possible attacks. The web app has to check the response coming from the ﬁle-system or the database in order to behave properly. For example, if a ﬁle is being read, the web app has to check that the ﬁle-system is answering with the uninterpreted function file() before proceeding further. Remote code execution Our formalization can represent scenarios where the attacker is able to write arbitrary ﬁles into the web app’s ﬁle-system leading to arbitrary remote code execution. As described earlier, a web app model is a sequence of if statements deﬁning the requests the web app responds to. The possibility of uploading a ﬁle that leads to code execution can be seen as a way of increasing the number of requests the web app responds to. We then include into the model of the web app a series of predeﬁned if branches representing the behavior of common malicious code an attacker might try to upload. We deﬁne

text: thus

text: representing

text: the

text: stateless

text: nature

text: of

text: HTTP.

text: The

text: web

text: app’s

text: model

text: is

text: thus

text: a

text: sequence

text: of

text: if

text: statements

text: deﬁning

text: all

text: the

text: requests

text: the

text: web

text: app

text: can

text: handle.

text: Client

text: communication

text: A

text: general

text: HTTP

text: request

text: (and

text: response)

text: header

text: comprises

text: diﬀerent

text: ﬁelds

text: that

text: are

text: needed

text: for

text: the

text: message

text: to

text: be

text: processed

text: by

text: the

text: browser.

text: In

text: our

text: formalization,

text: we

text: don’t

text: need

text: to

text: represent

text: all

text: the

text: ﬁelds

text: of

text: a

text: real

text: request

text: (or

text: response)

text: header

text: as

text: they

text: are

text: not

text: relevant

text: to

text: the

text: analysis,

text: and

text: thus

text: we

text: limit

text: to:

text: a

text: variable

text: representing

text: the

text: sender,

text: a

text: variable

text: representing

text: the

text: receiver,

text: and

text: a

text: concatenation

text: of

text: constants

text: and

text: variables

text: representing

text: the

text: message.

text: In

text: case

text: of

text: a

text: request,

text: the

text: message

text: would

text: be

text: represented

text: by

text: the

text: HTTP

text: query

text: string

text: containing

text: parameters

text: and

text: values.

text: For

text: example,

text: a

text: request

text: to

text: the

text: URL

text: can

text: be

text: represented

text: as

text: Client

text: WebApp

text: index.Page,

text: where

text: index

text: is

text: a

text: constant

text: representing

text: a

text: web

text: page

text: and

text: Page

text: is

text: a

text: variable

text: representing

text: an

text: HTTP

text: query

text: value.

text: We

text: proceed

text: similarly

text: to

text: formalize

text: a

text: response

text: from

text: the

text: web

text: app

text: to

text: the

text: client.

text: We

text: only

text: represent

text: the

text: details

text: needed

text: for

text: the

text: analysis:

text: a

text: constant

text: representing

text: the

text: returned

text: page

text: (e.g.,

text: dashboard,

text: admin

text: etc),

text: the

text: function

text: file()

text: when

text: the

text: web

text: app

text: performs

text: a

text: reading

text: operation

text: on

text: the

text: ﬁle-system,

text: and

text: the

text: function

text: tuple()

text: that,

text: following

text: is

text: returned

text: only

text: if

text: the

text: executed

text: query

text: is

text: SELECT,

text: UPDATE

text: or

text: DELETE.

text: For

text: example,

text: the

text: response

text: WebApp

text: Client

text: dashboard.file(fsi)

text: can

text: be

text: used

text: to

text: represent

text: the

text: result

text: of

text: a

text: successful

text: request

text: where

text: the

text: client

text: receives

text: the

text: dashboard

text: page.

text: The

text: message

text: file(fsi)

text: is

text: returned

text: to

text: express

text: that

text: a

text: ﬁle

text: was

text: retrieved

text: from

text: the

text: ﬁle-system.

text: File-system

text: and

text: database

text: communication

text: As

text: already

text: stated

text: in

text: whenever

text: the

text: web

text: app

text: has

text: to

text: read

text: content

text: from

text: the

text: ﬁle-system,

text: it

text: sends

text: a

text: readFile()

text: request

text: and

text: whenever

text: it

text: has

text: to

text: write

text: to

text: the

text: ﬁle-system,

text: it

text: sends

text: a

text: writeFile()

text: request.

text: When

text: the

text: web

text: app

text: has

text: to

text: perform

text: a

text: SQL

text: query

text: on

text: the

text: database,

text: it

text: sends

text: a

text: query()

text: request

text: to

text: the

text: database

text: (see

text: To

text: allow

text: the

text: web

text: app

text: to

text: represent

text: sanitized

text: input,

text: we

text: introduced

text: an

text: uninterpreted

text: function

text: sanitized()

text: that

text: allows

text: the

text: modeler

text: to

text: “switch

text: on”

text: or

text: “switch

text: oﬀ”

text: the

text: possi-

text: bility

text: of

text: exploiting

text: a

text: vulnerability

text: either

text: of

text: the

text: ﬁle-system

text: or

text: of

text: the

text: database,

text: letting

text: the

text: model-checker

text: analyze

text: the

text: web

text: app

text: for

text: possible

text: attacks.

text: The

text: web

text: app

text: has

text: to

text: check

text: the

text: response

text: coming

text: from

text: the

text: ﬁle-system

text: or

text: the

text: database

text: in

text: order

text: to

text: behave

text: properly.

text: For

text: example,

text: if

text: a

text: ﬁle

text: is

text: being

text: read,

text: the

text: web

text: app

text: has

text: to

text: check

text: that

text: the

text: ﬁle-system

text: is

text: answering

text: with

text: the

text: uninterpreted

text: function

text: file()

text: before

text: proceeding

text: further.

text: Remote

text: code

text: execution

text: Our

text: formalization

text: can

text: represent

text: scenarios

text: where

text: the

text: attacker

text: is

text: able

text: to

text: write

text: arbitrary

text: ﬁles

text: into

text: the

text: web

text: app’s

text: ﬁle-system

text: leading

text: to

text: arbitrary

text: remote

text: code

text: execution.

text: As

text: described

text: earlier,

text: a

text: web

text: app

text: model

text: is

text: a

text: sequence

text: of

text: if

text: statements

text: deﬁning

text: the

text: requests

text: the

text: web

text: app

text: responds

text: to.

text: The

text: possibility

text: of

text: uploading

text: a

text: ﬁle

text: that

text: leads

text: to

text: code

text: execution

text: can

text: be

text: seen

text: as

text: a

text: way

text: of

text: increasing

text: the

text: number

text: of

text: requests

text: the

text: web

text: app

text: responds

text: to.

text: We

text: then

text: include

text: into

text: the

text: model

text: of

text: the

text: web

text: app

text: a

text: series

text: of

text: predeﬁned

text: if

text: branches

text: representing

text: the

text: behavior

text: of

text: common

text: malicious

text: code

text: an

text: attacker

text: might

text: try

text: to

text: upload.

text: We

text: deﬁne


text: allow for generating multiple attack traces (nor do the other back-ends of the AVANTSSAR Platform). Thus, whenever a trace was found, we disabled the branch corresponding to the attack and run WAFEx again to generate another trace diﬀerent from the previous one. This process does, of course, miss some traces since by disabling a branch we prevent any other trace to use that branch in a diﬀerent step of the attack trace.7 However, it shows that multiple traces can actually be generated. We generated three diﬀerent AATs: #1, #2 and #3. AAT #1 This ﬁrst AAT shows how an attacker might be able to exploit an SQLi in the login phase to directly read ﬁles from the ﬁle-system (Listing 1.8). The attacker i sends to the web app a request for login by sending the payload sqli.fsi (1). The web app sends a query to the database entity (2), which forces the database into sending a read request to the ﬁle-system entity with value fsi (3). The ﬁle-system checks if the provided ﬁle is part of the ﬁle-system and answers to the database with that ﬁle (4). The database forwards the response from the ﬁle-system to the web app (5), which, ﬁnally, sends to the attacker the dashboard page along with the result from the database (6). Listing 1.8: AAT #1 for accessing the ﬁle-system in Multi-Stage. 1 i -> WebApp : login.sqli.fsi.Password 2 WebApp -> DB: query(sqli.fsi) 3 DB -> FS : readFile(fsi) 4 FS -> DB : file(fsi) 5 DB -> WebApp : tuple(file(fsi)) 6 WebApp -> i : dashboard.AuthCookie.tuple(file(fsi)) AAT #2 We disabled the branch that allows the database to read from the ﬁle-system and ran the model again in order to generate a diﬀerent AAT (Listing 1.9). The attacker i tries to exploit a SQLi in order to write a malicious ﬁle so to exploit a remote code execution. i sends to the web app a request for login by sending the payload sqli.evil_file (1). The web app sends a query to the database entity (2), which forces the database into sending a writing request with value evil_file to the ﬁle-system (3). The ﬁle-system marks the new ﬁle as available in the ﬁle-system and the database sends a response to the web app with the ﬁle just created (4). The web app responds to i with the dashboard page along with a newly generated cookie and the result of the creation of a new ﬁle (5). The attacker i now exploits the evil_file by sending the payload fsi to the web app (6). The web app will now perform a readFile() operation on the ﬁle-system and will send the retrieved ﬁle back to the attacker (7-9). Listing 1.9: AAT #2 for accessing the ﬁle-system in Multi-Stage. 1 i -> WebApp : login.sqli.evil_file.Password 2 WebApp -> DB: query(sqli.evil_file) 7 We plan to extend CL-AtSe or replace it with a tool capable of generating multiple attack traces. ##LTLine##

text: allow

text: for

text: generating

text: multiple

text: attack

text: traces

text: (nor

text: do

text: the

text: other

text: back-ends

text: of

text: the

text: AVANTSSAR

text: Platform).

text: Thus,

text: whenever

text: a

text: trace

text: was

text: found,

text: we

text: disabled

text: the

text: branch

text: corresponding

text: to

text: the

text: attack

text: and

text: run

text: WAFEx

text: again

text: to

text: generate

text: another

text: trace

text: diﬀerent

text: from

text: the

text: previous

text: one.

text: This

text: process

text: does,

text: of

text: course,

text: miss

text: some

text: traces

text: since

text: by

text: disabling

text: a

text: branch

text: we

text: prevent

text: any

text: other

text: trace

text: to

text: use

text: that

text: branch

text: in

text: a

text: diﬀerent

text: step

text: of

text: the

text: attack

text: However,

text: it

text: shows

text: that

text: multiple

text: traces

text: can

text: actually

text: be

text: generated.

text: We

text: generated

text: three

text: diﬀerent

text: AATs:

text: and

text: AAT

text: This

text: ﬁrst

text: AAT

text: shows

text: how

text: an

text: attacker

text: might

text: be

text: able

text: to

text: exploit

text: an

text: SQLi

text: in

text: the

text: login

text: phase

text: to

text: directly

text: read

text: ﬁles

text: from

text: the

text: ﬁle-system

text: (Listing

text: The

text: attacker

text: i

text: sends

text: to

text: the

text: web

text: app

text: a

text: request

text: for

text: login

text: by

text: sending

text: the

text: payload

text: sqli.fsi

text: The

text: web

text: app

text: sends

text: a

text: query

text: to

text: the

text: database

text: entity

text: which

text: forces

text: the

text: database

text: into

text: sending

text: a

text: read

text: request

text: to

text: the

text: ﬁle-system

text: entity

text: with

text: value

text: fsi

text: The

text: ﬁle-system

text: checks

text: if

text: the

text: provided

text: ﬁle

text: is

text: part

text: of

text: the

text: ﬁle-system

text: and

text: answers

text: to

text: the

text: database

text: with

text: that

text: ﬁle

text: The

text: database

text: forwards

text: the

text: response

text: from

text: the

text: ﬁle-system

text: to

text: the

text: web

text: app

text: which,

text: ﬁnally,

text: sends

text: to

text: the

text: attacker

text: the

text: dashboard

text: page

text: along

text: with

text: the

text: result

text: from

text: the

text: database

text: Listing

text: AAT

text: for

text: accessing

text: the

text: ﬁle-system

text: in

text: Multi-Stage.

text: i

text: WebApp

text: login.sqli.fsi.Password

text: WebApp

text: DB:

text: query(sqli.fsi)

text: DB

text: FS

text: readFile(fsi)

text: FS

text: DB

text: file(fsi)

text: DB

text: WebApp

text: tuple(file(fsi))

text: WebApp

text: i

text: dashboard.AuthCookie.tuple(file(fsi))

text: AAT

text: We

text: disabled

text: the

text: branch

text: that

text: allows

text: the

text: database

text: to

text: read

text: from

text: the

text: ﬁle-system

text: and

text: ran

text: the

text: model

text: again

text: in

text: order

text: to

text: generate

text: a

text: diﬀerent

text: AAT

text: (Listing

text: The

text: attacker

text: i

text: tries

text: to

text: exploit

text: a

text: SQLi

text: in

text: order

text: to

text: write

text: a

text: malicious

text: ﬁle

text: so

text: to

text: exploit

text: a

text: remote

text: code

text: execution.

text: i

text: sends

text: to

text: the

text: web

text: app

text: a

text: request

text: for

text: login

text: by

text: sending

text: the

text: payload

text: The

text: web

text: app

text: sends

text: a

text: query

text: to

text: the

text: database

text: entity

text: which

text: forces

text: the

text: database

text: into

text: sending

text: a

text: writing

text: request

text: with

text: value

text: to

text: the

text: ﬁle-system

text: The

text: ﬁle-system

text: marks

text: the

text: new

text: ﬁle

text: as

text: available

text: in

text: the

text: ﬁle-system

text: and

text: the

text: database

text: sends

text: a

text: response

text: to

text: the

text: web

text: app

text: with

text: the

text: ﬁle

text: just

text: created

text: The

text: web

text: app

text: responds

text: to

text: i

text: with

text: the

text: dashboard

text: page

text: along

text: with

text: a

text: newly

text: generated

text: cookie

text: and

text: the

text: result

text: of

text: the

text: creation

text: of

text: a

text: new

text: ﬁle

text: The

text: attacker

text: i

text: now

text: exploits

text: the

text: by

text: sending

text: the

text: payload

text: fsi

text: to

text: the

text: web

text: app

text: The

text: web

text: app

text: will

text: now

text: perform

text: a

text: readFile()

text: operation

text: on

text: the

text: ﬁle-system

text: and

text: will

text: send

text: the

text: retrieved

text: ﬁle

text: back

text: to

text: the

text: attacker

text: Listing

text: AAT

text: for

text: accessing

text: the

text: ﬁle-system

text: in

text: Multi-Stage.

text: i

text: WebApp

text: WebApp

text: DB:

text: We

text: plan

text: to

text: extend

text: CL-AtSe

text: or

text: replace

text: it

text: with

text: a

text: tool

text: capable

text: of

text: generating

text: multiple

text: attack

text: traces.

text: ##LTLine##


text: § running example we used in 1. The model is the one given in Listing 1.6 and as goal we used the one in Listing 1.7.8 Abstract Attack Trace We ran the model with WAFEx, which generated the AAT in Listing 1.12, which shows an attack that exploits a FI vulnerability allowing the attacker i to get access to the ﬁle-system. The attacker i sends a request for the include page along with a ﬁle inclusion payload represented by the constant fsi (1). The web app performs a read request to the ﬁle-system (2), which responds to the web app with the requested ﬁle (3), and the web app sends back the ﬁle (4) to the attacker. Listing 1.12: AAT that exploits a FI vulnerability. 1 i -> WebApp : include.fsi 2 WebApp -> FS: readFile(fsi) 3 FS -> WebApp: file(fsi) 4 WebApp -> i : include.file(fsi) C.2 Unrestricted File Upload (DVWA) In this case study, we used the UFU example from DVWA to show how simple it can be to represent an UFU vulnerability with our formalization. The example is indeed quite straightforward: a web app allows users to upload ﬁles. The model is shown in Listing 1.13. When it receives a request for ﬁle upload (1), the web app makes a request to the ﬁle-system entity for writing the ﬁle (2) and, since we assumed a writing operation always succeeds, the web app answers back to the client with the uploaded page (3). As goal, in Listing 1.14 we check that a malicious ﬁle, represented by the constant evil_file, is not part of the ﬁle-system. Abstract Attack Trace We ran the model with WAFEx, which generated the AAT in Listing 1.15, which shows an attack that exploits an UFU vul- nerability. The attacker i sends a request for uploading a ﬁle by sending the evil_file payload representing a malicious server side code (1). The web app sends a writing request to the ﬁle-system (2) and answers back to the client with the uploaded page. At the end of this execution, the ﬁle represented by the constant evil_file will be part of the ﬁle-system. Listing 1.13: Pseudo-code representing an UFU vulnerability. 1 if(Client -> WebApp : uploaded.File){ 2 WebApp -> FS : writeFile(File); 3 WebApp -> Client : uploaded;} 8 In our case studies, we use the variable Client when the web app is expecting an interaction with a client. Since we assumed only malicious interactions with the web § app ( 1), the variable Client will always be instantiated with the DY attacker i in concrete web app executions. ##LTLine##

text: running

text: example

text: we

text: used

text: in

text: The

text: model

text: is

text: the

text: one

text: given

text: in

text: Listing

text: and

text: as

text: goal

text: we

text: used

text: the

text: one

text: in

text: Listing

text: Abstract

text: Attack

text: Trace

text: We

text: ran

text: the

text: model

text: with

text: WAFEx,

text: which

text: generated

text: the

text: AAT

text: in

text: Listing

text: which

text: shows

text: an

text: attack

text: that

text: exploits

text: a

text: FI

text: vulnerability

text: allowing

text: the

text: attacker

text: i

text: to

text: get

text: access

text: to

text: the

text: ﬁle-system.

text: The

text: attacker

text: i

text: sends

text: a

text: request

text: for

text: the

text: include

text: page

text: along

text: with

text: a

text: ﬁle

text: inclusion

text: payload

text: represented

text: by

text: the

text: constant

text: fsi

text: The

text: web

text: app

text: performs

text: a

text: read

text: request

text: to

text: the

text: ﬁle-system

text: which

text: responds

text: to

text: the

text: web

text: app

text: with

text: the

text: requested

text: ﬁle

text: and

text: the

text: web

text: app

text: sends

text: back

text: the

text: ﬁle

text: to

text: the

text: attacker.

text: Listing

text: AAT

text: that

text: exploits

text: a

text: FI

text: vulnerability.

text: i

text: WebApp

text: include.fsi

text: WebApp

text: FS:

text: readFile(fsi)

text: FS

text: WebApp:

text: file(fsi)

text: WebApp

text: i

text: include.file(fsi)

text: Unrestricted

text: File

text: Upload

text: (DVWA)

text: In

text: this

text: case

text: study,

text: we

text: used

text: the

text: UFU

text: example

text: from

text: DVWA

text: to

text: show

text: how

text: simple

text: it

text: can

text: be

text: to

text: represent

text: an

text: UFU

text: vulnerability

text: with

text: our

text: formalization.

text: The

text: example

text: is

text: indeed

text: quite

text: straightforward:

text: a

text: web

text: app

text: allows

text: users

text: to

text: upload

text: ﬁles.

text: The

text: model

text: is

text: shown

text: in

text: Listing

text: When

text: it

text: receives

text: a

text: request

text: for

text: ﬁle

text: upload

text: the

text: web

text: app

text: makes

text: a

text: request

text: to

text: the

text: ﬁle-system

text: entity

text: for

text: writing

text: the

text: ﬁle

text: and,

text: since

text: we

text: assumed

text: a

text: writing

text: operation

text: always

text: succeeds,

text: the

text: web

text: app

text: answers

text: back

text: to

text: the

text: client

text: with

text: the

text: uploaded

text: page

text: As

text: goal,

text: in

text: Listing

text: we

text: check

text: that

text: a

text: malicious

text: ﬁle,

text: represented

text: by

text: the

text: constant

text: is

text: not

text: part

text: of

text: the

text: ﬁle-system.

text: Abstract

text: Attack

text: Trace

text: We

text: ran

text: the

text: model

text: with

text: WAFEx,

text: which

text: generated

text: the

text: AAT

text: in

text: Listing

text: which

text: shows

text: an

text: attack

text: that

text: exploits

text: an

text: UFU

text: vul-

text: nerability.

text: The

text: attacker

text: i

text: sends

text: a

text: request

text: for

text: uploading

text: a

text: ﬁle

text: by

text: sending

text: the

text: payload

text: representing

text: a

text: malicious

text: server

text: side

text: code

text: The

text: web

text: app

text: sends

text: a

text: writing

text: request

text: to

text: the

text: ﬁle-system

text: and

text: answers

text: back

text: to

text: the

text: client

text: with

text: the

text: uploaded

text: page.

text: At

text: the

text: end

text: of

text: this

text: execution,

text: the

text: ﬁle

text: represented

text: by

text: the

text: constant

text: will

text: be

text: part

text: of

text: the

text: ﬁle-system.

text: Listing

text: Pseudo-code

text: representing

text: an

text: UFU

text: vulnerability.

text: if(Client

text: WebApp

text: uploaded.File){

text: WebApp

text: FS

text: writeFile(File);

text: WebApp

text: Client

text: uploaded;}

text: In

text: our

text: case

text: studies,

text: we

text: use

text: the

text: variable

text: Client

text: when

text: the

text: web

text: app

text: is

text: expecting

text: an

text: interaction

text: with

text: a

text: client.

text: Since

text: we

text: assumed

text: only

text: malicious

text: interactions

text: with

text: the

text: web

text: app

text: the

text: variable

text: Client

text: will

text: always

text: be

text: instantiated

text: with

text: the

text: DY

text: attacker

text: i

text: in

text: concrete

text: web

text: app

text: executions.

text: ##LTLine##


text: Listing 1.14: Goal representing that a malicious ﬁle has been uploaded to the web application’s ﬁle-system. [](! inFS(evil_file )); Listing 1.15: AAT that exploits an UFU vulnerability. 1 i -> WebApp : uploaded.evil_file 2 WebApp -> FS: writeFile(evil_file) 3 WebApp -> i : uploaded C.3 SQLi read (DVWA) In this case study, we used the SQLi example from DVWA to show how it is possible to exploit a SQLi for reading content from the ﬁle-system. This example from DVWA was meant to show how a SQLi vulnerability can be exploited for extracting data from the database. However, WAFEx was able to generate a wider set of attack traces showing that the SQLi in DVWA could also be used for reading ﬁles from the ﬁle-system. Consider a web app that accepts a value representing a user id that is used in a SELECT query for retrieving and showing details about that user. The model is given in Listing 1.16. The web app accepts a request for the userid page along with the IDvalue value (1). The web app then performs a query to the database by sending a query request (2). The web app waits to receive back the result of the query from the database (3) and, upon receiving tuple(Response), it sends to the user the page userid and the result of the query tuple(Response). Listing 1.17 shows the ﬁle-system access goal that we deﬁned in which the attacker should not be able to know file(). Listing 1.16: Pseudo-code representing a SQLi for ﬁle reading vulnerability. 1 if(Client -> WebApp : userid.IDvalue){ 2 WebApp -> DB : query(IDvalue); 3 if(DB -> WebApp : tuple(Response )){ 4 WebApp -> Client: userid.tuple(Response );}} Listing 1.17: Goal representing that the attacker knows the content of the ﬁle- system. [](! iknowledge(file (*))); Abstract Attack Trace We ran the model with WAFEx, which generated the AAT in Listing 1.18, which shows an attack in which the attacker i is able to exploit a SQLi vulnerability in order to read from the ﬁle-system. The attacker i sends the concatenation of userid with the SQLi payload sqli and the fsi payload (1). The web app sends a query to the database (2), which, thanks to

text: Listing

text: Goal

text: representing

text: that

text: a

text: malicious

text: ﬁle

text: has

text: been

text: uploaded

text: to

text: the

text: web

text: application’s

text: ﬁle-system.

text: Listing

text: AAT

text: that

text: exploits

text: an

text: UFU

text: vulnerability.

text: i

text: WebApp

text: WebApp

text: FS:

text: WebApp

text: i

text: uploaded

label: section

text: SQLi

text: read

text: (DVWA)

text: In

text: this

text: case

text: study,

text: we

text: used

text: the

text: SQLi

text: example

text: from

text: DVWA

text: to

text: show

text: how

text: it

text: is

text: possible

text: to

text: exploit

text: a

text: SQLi

text: for

text: reading

text: content

text: from

text: the

text: ﬁle-system.

text: This

text: example

text: from

text: DVWA

text: was

text: meant

text: to

text: show

text: how

text: a

text: SQLi

text: vulnerability

text: can

text: be

text: exploited

text: for

text: extracting

text: data

text: from

text: the

text: database.

text: However,

text: WAFEx

text: was

text: able

text: to

text: generate

text: a

text: wider

text: set

text: of

text: attack

text: traces

text: showing

text: that

text: the

text: SQLi

text: in

text: DVWA

text: could

text: also

text: be

text: used

text: for

text: reading

text: ﬁles

text: from

text: the

text: ﬁle-system.

text: Consider

text: a

text: web

text: app

text: that

text: accepts

text: a

text: value

text: representing

text: a

text: user

text: id

text: that

text: is

text: used

text: in

text: a

text: SELECT

text: query

text: for

text: retrieving

text: and

text: showing

text: details

text: about

text: that

text: user.

text: The

text: model

text: is

text: given

text: in

text: Listing

text: The

text: web

text: app

text: accepts

text: a

text: request

text: for

text: the

text: userid

text: page

text: along

text: with

text: the

text: IDvalue

text: value

text: The

text: web

text: app

text: then

text: performs

text: a

text: query

text: to

text: the

text: database

text: by

text: sending

text: a

text: query

text: request

text: The

text: web

text: app

text: waits

text: to

text: receive

text: back

text: the

text: result

text: of

text: the

text: query

text: from

text: the

text: database

text: and,

text: upon

text: receiving

text: tuple(Response),

text: it

text: sends

text: to

text: the

text: user

text: the

text: page

text: userid

text: and

text: the

text: result

text: of

text: the

text: query

text: tuple(Response).

text: Listing

text: shows

text: the

text: ﬁle-system

text: access

text: goal

text: that

text: we

text: deﬁned

text: in

text: which

text: the

text: attacker

text: should

text: not

text: be

text: able

text: to

text: know

text: file().

text: Listing

text: Pseudo-code

text: representing

text: a

text: SQLi

text: for

text: ﬁle

text: reading

text: vulnerability.

text: if(Client

text: WebApp

text: userid.IDvalue){

text: WebApp

text: DB

text: query(IDvalue);

text: if(DB

text: WebApp

text: tuple(Response

text: WebApp

text: Client:

text: userid.tuple(Response

text: Listing

text: Goal

text: representing

text: that

text: the

text: attacker

text: knows

text: the

text: content

text: of

text: the

text: ﬁle-

text: system.

text: iknowledge(file

text: Abstract

text: Attack

text: Trace

text: We

text: ran

text: the

text: model

text: with

text: WAFEx,

text: which

text: generated

text: the

text: AAT

text: in

text: Listing

text: which

text: shows

text: an

text: attack

text: in

text: which

text: the

text: attacker

text: i

text: is

text: able

text: to

text: exploit

text: a

text: SQLi

text: vulnerability

text: in

text: order

text: to

text: read

text: from

text: the

text: ﬁle-system.

text: The

text: attacker

text: i

text: sends

text: the

text: concatenation

text: of

text: userid

text: with

text: the

text: SQLi

text: payload

text: sqli

text: and

text: the

text: fsi

text: payload

text: The

text: web

text: app

text: sends

text: a

text: query

text: to

text: the

text: database

text: which,

text: thanks

text: to


text: Listing 1.3: PHP code for uploading a ﬁle. 1 $path="uploads/"; 2 // where the file will be saved 3 $target_path = $target_path.basename($_FILES[’ uploadedfile’][’name’]); 4 // move uploaded file from tmp directory to target path 5 if(move_uploaded_file($_FILES[’uploadedfile’][’tmp_name’ ],$target_path)){ 6 echo "file " . basename($_FILES[’uploadedfile’][’name’ ]) . " uploaded!"; 7 }else { echo "there was an error uploading the file"; } UFU can also be used in combination with DT, allowing the attacker to overwrite arbitrary ﬁles stored in the web server. However, modern web app programming languages (like PHP) perform a sanitization on the uploaded ﬁle path string by removing any special characters such as “..” and “/” used to change the current path, making the exploitation of a DT less likely to happen. 3 A formalization to reason about ﬁle-system vulnerabilities We will now describe how we formally represent the behavior of a ﬁle-system and of a web app that interacts with it. We also show how our formaliza- tion allows the DY attacker to successfully exploit ﬁle-system vulnerabilities. In our formalization, we used ASLan++, the formal speciﬁcation language of the AVANTSSAR Platform [3], but in fact our approach is general and for the sake of readability we give here pseudo-code rather than ASLan++. (see the appendix for the full ASLan++ code). Our approach doesn’t search for payloads that can be used to exploit ﬁle- system vulnerabilities, but rather analyzes the security of web apps by exploiting vulnerabilities that lead attackers to have unauthorized access to the ﬁle-system. To deal with such vulnerabilities, we need to represent the behavior of the (i) web app, which deﬁnes the interaction with the client, the ﬁle-system and the database, (ii) ﬁle-system, which interacts with the web app and the database for reading and writing content, (iii) database, which can also interact with the ﬁle-system, (iv) attacker, who interacts only with the web app. We do not formalize the behavior of honest clients since we assume the DY attacker to be the only agent to communicate with the web app, i.e., we are only interested in dishonest interactions. This is because the exploitation of ﬁle- system vulnerabilities doesn’t require interaction with the honest users. To explain how our formalization works, we will use a simple FI example depicted in Fig. 1 as a Message Sequence Chart (MSC) in which there are three

text: Listing

text: PHP

text: code

text: for

text: uploading

text: a

text: ﬁle.

text: $path="uploads/";

text: where

text: the

text: file

text: will

text: be

text: saved

text: uploadedfile’][’name’]);

text: move

text: uploaded

text: file

text: from

text: tmp

text: directory

text: to

text: target

text: path

text: echo

text: "file

text: uploaded!";

text: }else

text: echo

text: "there

text: was

text: an

text: error

text: uploading

text: the

text: file";

text: UFU

text: can

text: also

text: be

text: used

text: in

text: combination

text: with

text: DT,

text: allowing

text: the

text: attacker

text: to

text: overwrite

text: arbitrary

text: ﬁles

text: stored

text: in

text: the

text: web

text: server.

text: However,

text: modern

text: web

text: app

text: programming

text: languages

text: (like

text: PHP)

text: perform

text: a

text: sanitization

text: on

text: the

text: uploaded

text: ﬁle

text: path

text: string

text: by

text: removing

text: any

text: special

text: characters

text: such

text: as

text: and

text: used

text: to

text: change

text: the

text: current

text: path,

text: making

text: the

text: exploitation

text: of

text: a

text: DT

text: less

text: likely

text: to

text: happen.

text: A

text: formalization

text: to

text: reason

text: about

text: ﬁle-system

text: vulnerabilities

text: We

text: will

text: now

text: describe

text: how

text: we

text: formally

text: represent

text: the

text: behavior

text: of

text: a

text: ﬁle-system

text: and

text: of

text: a

text: web

text: app

text: that

text: interacts

text: with

text: it.

text: We

text: also

text: show

text: how

text: our

text: formaliza-

text: tion

text: allows

text: the

text: DY

text: attacker

text: to

text: successfully

text: exploit

text: ﬁle-system

text: vulnerabilities.

text: In

text: our

text: formalization,

text: we

text: used

text: ASLan++,

text: the

text: formal

text: speciﬁcation

text: language

text: of

text: the

text: AVANTSSAR

text: Platform

text: but

text: in

text: fact

text: our

text: approach

text: is

text: general

text: and

text: for

text: the

text: sake

text: of

text: readability

text: we

text: give

text: here

text: pseudo-code

text: rather

text: than

text: ASLan++.

text: (see

text: the

text: appendix

text: for

text: the

text: full

text: ASLan++

text: code).

text: Our

text: approach

text: doesn’t

text: search

text: for

text: payloads

text: that

text: can

text: be

text: used

text: to

text: exploit

text: ﬁle-

text: system

text: vulnerabilities,

text: but

text: rather

text: analyzes

text: the

text: security

text: of

text: web

text: apps

text: by

text: exploiting

text: vulnerabilities

text: that

text: lead

text: attackers

text: to

text: have

text: unauthorized

text: access

text: to

text: the

text: ﬁle-system.

text: To

text: deal

text: with

text: such

text: vulnerabilities,

text: we

text: need

text: to

text: represent

text: the

text: behavior

text: of

text: the

text: (i)

text: web

text: app,

text: which

text: deﬁnes

text: the

text: interaction

text: with

text: the

text: client,

text: the

text: ﬁle-system

text: and

text: the

text: database,

text: (ii)

text: ﬁle-system,

text: which

text: interacts

text: with

text: the

text: web

text: app

text: and

text: the

text: database

text: for

text: reading

text: and

text: writing

text: content,

text: (iii)

text: database,

text: which

text: can

text: also

text: interact

text: with

text: the

text: ﬁle-system,

text: (iv)

text: attacker,

text: who

text: interacts

text: only

text: with

text: the

text: web

text: app.

text: We

text: do

text: not

text: formalize

text: the

text: behavior

text: of

text: honest

text: clients

text: since

text: we

text: assume

text: the

text: DY

text: attacker

text: to

text: be

text: the

text: only

text: agent

text: to

text: communicate

text: with

text: the

text: web

text: app,

text: i.e.,

text: we

text: are

text: only

text: interested

text: in

text: dishonest

text: interactions.

text: This

text: is

text: because

text: the

text: exploitation

text: of

text: ﬁle-

text: system

text: vulnerabilities

text: doesn’t

text: require

text: interaction

text: with

text: the

text: honest

text: users.

text: To

text: explain

text: how

text: our

text: formalization

text: works,

text: we

text: will

text: use

text: a

text: simple

text: FI

text: example

text: depicted

text: in

text: Fig.

text: as

text: a

text: Message

text: Sequence

text: Chart

text: (MSC)

text: in

text: which

text: there

text: are

text: three


text: Hybrid PDE solver for data-driven problems and modern branching 11 set of particles. We start a particle at x at time 0, this particle has a life time τ which is exponentially distributed with intensity c (sometimes known as the “branching rate”), we then simulate this particle until min(t, τ, τ ), where τ is the particle hitting the ∂Ω ∂Ω spatial boundary, if τ is this smallest time, then the particle “branches” into i particles with probability α . These particles all start at the same point in space, however, they i are all equipped with the own independent exponential random variable (“life time”) and driving Brownian motion. We then continue to simulate every particle until it has hit the space boundary or is alive at time t. We provide a detailed algorithm for branching diffusions (without space boundaries) in Section . Consider the same initial and boundary value as above. The solution u can then be written as the expected value of the product of the surviving particles or particles that hit the space boundar(cid:34)y (see [7]), (cid:35) (cid:89) (cid:16) (cid:0) (cid:1) (cid:0) (cid:1) (cid:17) u(x, t) = Ex,0 Nt ψ Xt(i) 1{t<τ∂Ω} + g Xτ(∂i)Ω, t − τ∂Ω 1{t≥τ∂Ω} , (3.2) i=1 where X(i) is the location of the ith particle surviving at time s and N is the number s t of surviving particles at time t (a particle that hits the boundary is still “alive” at time t). Although this set up allows for more general PDEs, it is not difﬁcult to see that the computational complexity is greater for these types of problems (though still smaller than that for FBSDEs). Moreover, because of the nature of the branching, we are mainly conﬁned to cases which are not “overly” nonlinear with time horizons that are not too long. Otherwise, we may end up with “explosions” whereby we are required to keep track of an extremely large number of particles, which will also tend to increase the number of branchings. We postpone discussion of this to Section . To help give an idea of branching diffusions we illustrate a sample path for a given (cid:0) (cid:1) PDE. Let us consider the PDE (one spatial dimension), ∂u − ∂2u − 1 ∈ R 1 + u2 + u = 0, u(x, 0) = ψ(x), x , t > 0. ∂t ∂x2 2 From the work above there are two possible outcomes at a branching time (compare with (3.1)), either the particle dies, or splits into two descendants, the probability of each of these events is 1. A possible trajectory (to compute u(x , T)) is shown in Figure . 2 0 3.1.1 A PDD numerical example with the KPP Equation Since we already have enough machinery to consider some interesting PDEs let us show an example which comes from the area of reaction diffusion equations, this class of equations are used in many areas such as physics and biology [31], [32], [48]. For illus- tration purposes we consider the most well known of these, the Kolmogorov-Petrovsky- Piskunov (KPP) equation [47], linked to applications in plasma physics and ecology. The general form of the KPP is the following nonlinear parabolic PDE, ∂u − ∂2u − ∈ R × ∞ D + ru(1 u) = 0 , (x, t) [0, ) ∂t ∂x2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Hybrid

font: NMKSAB+CharterBT-Italic

text: PDE

text: solver

text: for

text: data-driven

text: problems

text: and

text: modern

text: branching

font: TAAMUF+CharterBT-Roman

text: set

text: of

text: particles.

text: We

text: start

text: a

text: particle

text: at

text: x

text: at

text: time

text: this

text: particle

text: has

text: a

text: life

text: time

text: τ

text: which

text: is

text: exponentially

text: distributed

text: with

text: intensity

text: c

text: (sometimes

text: known

text: as

text: the

text: “branching

text: rate”),

text: we

text: then

text: simulate

text: this

text: particle

text: until

text: min(t,

text: τ,

text: τ

text: where

text: τ

text: is

text: the

text: particle

text: hitting

text: the

text: ∂Ω

text: ∂Ω

text: spatial

text: boundary,

text: if

text: τ

text: is

text: this

text: smallest

text: time,

text: then

text: the

text: particle

text: “branches”

text: into

text: i

text: particles

text: with

text: probability

text: α

text: These

text: particles

text: all

text: start

text: at

text: the

text: same

text: point

text: in

text: space,

text: however,

text: they

text: i

text: are

text: all

text: equipped

text: with

text: the

text: own

text: independent

text: exponential

text: random

text: variable

text: (“life

text: time”)

text: and

text: driving

text: Brownian

text: motion.

text: We

text: then

text: continue

text: to

text: simulate

text: every

text: particle

text: until

text: it

text: has

text: hit

text: the

text: space

text: boundary

text: or

text: is

text: alive

text: at

text: time

text: t.

text: We

text: provide

text: a

text: detailed

text: algorithm

text: for

text: branching

text: diffusions

text: (without

text: space

text: boundaries)

text: in

text: Section

text: Consider

text: the

text: same

text: initial

text: and

text: boundary

text: value

text: as

text: above.

text: The

text: solution

text: u

text: can

text: then

text: be

text: written

text: as

text: the

text: expected

text: value

text: of

text: the

text: product

text: of

text: the

text: surviving

text: particles

text: or

text: particles

text: that

text: hit

text: the

text: space

text: (see

text: u(x,

text: t)

text: Nt

text: ψ

text: Xt(i)

text: g

text: Xτ(∂i)Ω,

text: t

text: τ∂Ω

text: 1{t≥τ∂Ω}

text: where

text: X(i)

text: is

text: the

text: location

text: of

text: the

text: ith

text: particle

text: surviving

text: at

text: time

text: s

text: and

text: N

text: is

text: the

text: number

text: s

text: t

text: of

text: surviving

text: particles

text: at

text: time

text: t

text: (a

text: particle

text: that

text: hits

text: the

text: boundary

text: is

text: still

text: “alive”

text: at

text: time

text: t).

text: Although

text: this

text: set

text: up

text: allows

text: for

text: more

text: general

text: PDEs,

text: it

text: is

text: not

text: difﬁcult

text: to

text: see

text: that

text: the

text: computational

text: complexity

text: is

text: greater

text: for

text: these

text: types

text: of

text: problems

text: (though

text: still

text: smaller

text: than

text: that

text: for

text: FBSDEs).

text: Moreover,

text: because

text: of

text: the

text: nature

text: of

text: the

text: branching,

text: we

text: are

text: mainly

text: conﬁned

text: to

text: cases

text: which

text: are

text: not

text: “overly”

text: nonlinear

text: with

text: time

text: horizons

text: that

text: are

text: not

text: too

text: long.

text: Otherwise,

text: we

text: may

text: end

text: up

text: with

text: “explosions”

text: whereby

text: we

text: are

text: required

text: to

text: keep

text: track

text: of

text: an

text: extremely

text: large

text: number

text: of

text: particles,

text: which

text: will

text: also

text: tend

text: to

text: increase

text: the

text: number

text: of

text: branchings.

text: We

text: postpone

text: discussion

text: of

text: this

text: to

text: Section

text: To

text: help

text: give

text: an

text: idea

text: of

text: branching

text: diffusions

text: we

text: illustrate

text: a

text: sample

text: path

text: for

text: a

text: given

text: PDE.

text: Let

text: us

text: consider

text: the

text: PDE

text: (one

text: spatial

text: dimension),

text: ∂u

text: R

text: u

text: u(x,

text: ψ(x),

text: x

text: t

text: ∂t

text: From

text: the

text: work

text: above

text: there

text: are

text: two

text: possible

text: outcomes

text: at

text: a

text: branching

text: time

text: (compare

text: with

text: either

text: the

text: particle

text: dies,

text: or

text: splits

text: into

text: two

text: descendants,

text: the

text: probability

text: of

text: each

text: of

text: these

text: events

text: is

text: A

text: possible

text: trajectory

text: (to

text: compute

text: u(x

text: T))

text: is

text: shown

text: in

text: Figure

text: A

text: PDD

text: numerical

text: example

text: with

text: the

text: KPP

text: Equation

text: Since

text: we

text: already

text: have

text: enough

text: machinery

text: to

text: consider

text: some

text: interesting

text: PDEs

text: let

text: us

text: show

text: an

text: example

text: which

text: comes

text: from

text: the

text: area

text: of

text: reaction

text: diffusion

text: equations,

text: this

text: class

text: of

text: equations

text: are

text: used

text: in

text: many

text: areas

text: such

text: as

text: physics

text: and

text: biology

text: For

text: illus-

text: tration

text: purposes

text: we

text: consider

text: the

text: most

text: well

text: known

text: of

text: these,

text: the

text: Kolmogorov-Petrovsky-

text: Piskunov

text: (KPP)

text: equation

text: linked

text: to

text: applications

text: in

text: plasma

text: physics

text: and

text: ecology.

text: The

text: general

text: form

text: of

text: the

text: KPP

text: is

text: the

text: following

text: nonlinear

text: parabolic

text: PDE,

text: ∂u

text: R

text: D

text: u)

text: (x,

text: t)

text: ∂t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##