Roland Bacher

The Stern Sequence and Moments of Minkowski's Question Mark Function

We use properties of the Stern Sequence for numerical computations of moments 1 0 t n d?(t) associated to Minkowski's Question Mark function.

Introduction

Minkowski's question mark function x -→?(x) and its inverse function, Conway's box function x -→ 2(x), are related to continued fraction expansions, transcendence properties and probabilistic distributions of rationals in the Calkin-Wilf tree. Denjoy proved apparently that ?(x) is monotonic continuous and singular (derivable on a set of full measure with zero derivative on this set), see [START_REF] Denjoy | Sur une fonction réelle de Minkowski[END_REF]. Using a functional equation satisfied by ?(x), Alkauskas investigated the sequence m 0 , m 1 , . . . , m n = 1 0 x n d?(s) of moments of the probability density d? in a series of articles. Denoting by 2(y) the reciprocal function, known as Conway's Box function, of the increasing homeomorphism ? : [0, 1] -→ [0, 1], the substitution t =?(x) (with d?(x) = dt and x = 2(t)) yields

m n = 1 0 (2(t)) n dt . (1)
In the present paper we link these moments to the Stern sequence (which underlies the Calkin-Wilf tree) s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n + 1) = s(n) + s(n + 1), n ≥ 1. This gives new proofs for many results of Alkauskas, see for example [START_REF] Alkauskas | Explicit Series for the dyadic Period Function and Moments[END_REF], [START_REF] Alkauskas | The Moments of Minkowski Question Mark Function: The Dyadic Period Function[END_REF], [START_REF] Alkauskas | An asymptotic Formula for the Moments of Minkowski Question Mark Function in the Interval[END_REF]. It also leads to the discovery of some new properties.

The sequel of the paper is organized as follows: Section 2 links the Stern sequence with Conway's Box function 2 appearing in (1).

1 Keywords: Minkowski's Question Mark Function, Conway's Box Function, Stern sequence, Farey Sequence, Continued Fraction. Math. class: Primary: 11A55, Secondary: 11B57.

1 Section 3 recalls properties of Minkowski's question mark function. Section 4 lists a few well-known identities among binomial coefficients and elements of the Stern sequence for later use.

Section 5 presents a set of linear relations obtained by considering Riemann sums for 1 0 2(x) n dx. These relations differ from the relations found by Alkauskas: they are perhaps slightly simpler but more interestingly, a crude spectral analysis of the underlying linear operator T is easy. T has a unique eigenvector (m 0 , m 1 , m 2 , . . . ) of eigenvalue 1. All other eigenvalues belong to the closed complex disc of radius 1/2. The maximal error of the associated algorithm is thus roughly halved at each iteration.

Section 6 discusses a different set of Riemann sums which leads to linear relations used by Alkauskas. We extend in Section 7 the moment-function n -→ m n to an entire function z -→ m z for z ∈ C.

A computation of the derivative of this function at 0 to high accuracy suggests the conjectural identities

log 2 = ∞ n=1 m n 2n 1 + 1 2 n-1 = ∞ n=1 m n n 1 2 n -(-1) n
given in Section 8.

Section 9 introduces a third type of Riemann sums, particularly well suited for asymptotic computations. The resulting asymptotic formula

m n ∼ ∞ j=0 (log 2) j j! m j ∞ h=2 1 2 h 1 - 1 h n (2)
is the object of Section 10. It is more complicated but experimentally more accurate than Alkauskas's asymptotic formula given in [START_REF] Alkauskas | An asymptotic Formula for the Moments of Minkowski Question Mark Function in the Interval[END_REF]. Alkauskas's formula can however be deduced from (2) by a simple application of Laplace's method. Section 10.2 derives a second asymptotic formula related to (2) by a finer subdivision in the underlying Riemann sum. Since this should lead to slightly more accurate results, we consider (admittedly in a not completely rigorous way) in Section 10.3 the difference between the two formulae as a measure of accuracy for [START_REF] Alkauskas | The Moments of Minkowski Question Mark Function: The Dyadic Period Function[END_REF].

Section 11 is devoted to values m -n of moments at negative integers. This leads to a sequence of identities among m 0 , m 1 , m 2 , . . . . The two initial identities are Finally, Section 12 discusses the starting point of this work: asymptotics for 2 n+1 j=2 n s j allowing to compute some geometric means for values of the Stern sequence.

Conway's box function

We denote by D = Z[1/2] ∩ [0, 1] the subset of all rational dyadic numbers in [0,[START_REF] Alkauskas | Explicit Series for the dyadic Period Function and Moments[END_REF]. The restriction to D of Conway's Box function 2 is recursively defined as follows: 2(0) = 0, 2(1) = 1 and The main tool used in this paper is the following simple observation which defines 2 on D in terms of the Stern-sequence: Proposition 2.1. We have

2 2m + 1 2 n+1 = a + c b + d if 2 m 2 n =
2 m 2 n = s(m) s(2 n + m) for all natural integers m, n such that 0 ≤ m ≤ 2 n .
We leave the easy proof to the reader.

2 Since a b < c d with bd > 0 implies a b < a+c b+d < c d , the function 2 is strictly increasing. Induction on k shows 2 m 2 n ± 1 2 n+k = ka + c kb + d , k ≥ 1 (3) if 2 m 2 n = a b and 2 m 2 n ± 1 2 n = c d (
: [0, 1] -→ [0, 1]. Since lim k→∞ 2 m 2 n ± 1 2 n+k -2 m 2 n ±2 -n-k = 2 n+k b(kb + d) = ∞,
the function 2 has a vertical tangent at dyadic arguments.

Proposition 2.2. We have

2(x) = 1 -2(1 -x) . (4)
Proof. Continuity of Conway's Box function implies that it is enough to prove Proposition 2.2 for all dyadic rationals of the form m 2 n . This is done by induction using the trivial identity a+c b+d = 1 -b-a+d-c b+d .

Corollary 2.3. The function

x -→ 22 x -1 2 -1 is symmetric. Thus we have 0 = 1 0 (2(x) -1/2) 2n+1 dx = 2n+1 k=0 2n + 1 k (-2) k-2n-1 m k (5)
for every odd natural number 2n + 1. This can be restated as:

Corollary 2.4. For all n ≥ 0 we have the identity

m 2n+1 = 1 2 2n+1 2n k=0 (-2) k 2n + 1 k m k . (6)
In particular, m 2n+1 is a Z 1 2 -linear combination of m 0 , m 2 , m 4 , . . . , m 2n .

Minkowski's question mark function

Given an irrational real number x in (0, 1) with continued fraction expansion given by

x = [0; a 1 , a 2 , a 3 , . . . ] = 1 a 1 + 1 a 2 +...

,

Minkowski's question mark function is defined by

?(x) = -2 ∞ k=1 (-1) k 2 a 1 +•••+a k . ( 7
) Proposition 3.1. Minkowski's question mark function is an increasing homeomorphism of [0, 1] such that 2•?(x) =? • 2(x) = x.
Proof (given for the sake of self-containedness). Since 2 is an increasing homeomorphism of [0, 1], it is enough to prove that 2•?(x) = x for every rational number x in [0, 1]. We show this by induction on the length n of the continued fraction expansion x = [0; a 1 , a 2 , . . . , a n ] of x. The result clearly holds for n = 0 (corresponding to x = 0) and for n = 1 (corresponding to the inverse of a non-zero natural integer). Writing p k q k = [0; a 1 , . . . , a k ] we have

? p n-1 q n-1 = -2 n-1 j=1 (-1) j 2 a 1 +•••+a j = m 2 a 1 +•••+a n-1 -1
for a suitable natural number m. We also have

? p n-2 q n-2 =? p n-1 q n-1 - (-1) n 2 a 1 +•••+a n-1 -1 .

Using the induction hypothesis

p k q k = 2•? p k q k
for k < n and applying (3) to ?

p n q n = m 2 a 1 +•••+a n-1 -1 - (-1) n 2 an 2 a 1 +•••+a n-1 -1 we get 2•? p n q n = a n p n-1 + p n-2 a n q n-1 + q n-2 = p n q n .
The graph of ? is well-known to behave in a self-similar way as shown by the following well-known result: Proposition 3.2. We have

?(1 -x) = 1-?(x) (8)
and

? x 1 + x = 1 2 ?(x) (9)
for all x ∈ [0, 1].

Proof. Identity (8) follows from Proposition 2.2 and Proposition 3.1. Identity 9 follows from the Definition (7) applied to

x 1+x = 1 1+1/x = [0; 1 + a 1 , a 2 , a 3 , . . . ].
The aim of this paper is to study the moments

m z = 1 0 2(t) z dt = 1 0 x z d?(x)
of the probability measure d? associated to the distribution function ?(x) = x 0 d?(t). The inequalities

∞ n=1 1 2 n 1 - 1 n j ≤ m j ≤ 2 ∞ n=1 1 2 n 1 - 1 n j coming from the evaluation 2(1 -2 -m ) = 1 -1 m+1
, and the trivial upper bound -z-j+1

j ≤ |z|+j-1 j ≤ (|z| + j) |z| show that z → m z is an entire function of C.
The function m z is also given by the expression

m z = ∞ k=0 z + k -1 k γ(k + z)m k
(see ( 24)) where γ(z) is the entire function defined by

γ(z) = ∞ n=1 1 2 n 1 (1 + n) z .
We give the series expansion of the entire function z → m z at z = 0 and study the asymptotics of m z for real z -→ ±∞. Proposition 3.3. We have the identities

m z = ∞ j=0 z j (-1) j m j = ∞ j=0 -z + j -1 j m j where z j = z(z-1)(z-2)•••(z-j+1) j!
.

The main contribution to m -k given by Proposition 3.3 corresponds to indices j such that k+j j e - √ (log 2)/j ∼ 1 yielding j ∼ k 2 log 2 . Thus we have for example

m -1 = ∞ n=0 m n m -2 = ∞ n=0 (n + 1)m n m -3 = 1 2 ∞ n=0 (n + 1)(n + 2)m n
and more generally

m -n = ∞ k=0 k + n -1 n -1 m k .
Proof of Proposition 3.3. Proposition 2.2 implies the equalities

m z = 1 0 2(t) z dt = 1 0 (1-2(t)) z dt = ∞ j=0 z j (-1) j m j = ∞ j=0 -z + j -1 j m j
which hold for all z ∈ C since 2(t) ∈ (0, 1) for t ∈ (0, 1).

A few useful identities

Almost all results of this paper are based on a few trivial identities, recorded in this Section for later use.

Binomial coefficients

Lemma 4.1. We have the series expansion

1 (1 -x) n = ∞ k=0 n + k -1 k x k = ∞ k=0 n + k -1 n -1 x k (10)
for x in the open complex unit-disc.

Proof. Apply the equality

-n k = (-1) k n+k-1 k (where x k = x(x-1)•••(x-k+1) k! ) to Newton's identity (1 + (-x)) -n = ∞ k=0 -n k (-x) k or use induction on n.
Remark 4.2. Lemma 4.1 has the following nice combinatorial proof:

1 (1-x) n
is the generating series for colouring Easter eggs with n different colours (or, equivalently, for the number of monomials in n commuting variables). The k-th coefficient is thus given by k+n-1 n-1 . Lemma 4.3. We have

j l=k j l l k x l = j k x k (x + 1) j-k
In particular, for x = -1 2 we get

j l=k j l l k 1 (-2) l = j k (-1) k 2 j
Proof. Compare the coefficients j l l k and j k j-k l-k of x l of both sides.

Identities for the Stern sequence

We recall that the Stern sequence s : N -→ N is recursively defined by s(0) = 0, s(1) = 1, s(2n) = s(n) and s(2n + 1) = s(n) + s(n + 1) for n ≥ 1.

Proposition 4.4. For all n ≥ 0 and for all r such that 0 ≤ r ≤ 2 n , the Stern sequence satisfies the identities

s(2 n + r) = s(2 n -r) + s(r), (11)
s(2 n + r) = s(2 n+1 -r), (12)
s(r) = 2s(2 n + r) -s(3 • 2 n + r). (13)
Proof. The identities hold for n = 0 and r ∈ {0, 1}. Since s(2m) = s(m) they hold for r even by induction. For odd r = 2t + 1 < 2 n+1 , we sum the identities corresponding to (n -1, t) and (n -1, t + 1) which hold by induction. The definition s(2m + 1) = s(m)+ s(m + 1) and induction implies the identities for odd r.

The main idea of this paper is to apply Lemma 4.1 to the trivial identities

αs + βS γs + δS = α δ s S 1 1 + γ δ s S + β δ 1 1 + γ δ s S , ( 14
)
αs + βS γs + δS = α γ + β δ - α γ 1 1 + γ δ s S , ( 15
)
αs + βS γs + δS , = β δ + α δ - βγ δ 2 s S 1 1 + γ δ s S . ( 16
)
5 A simple set of linear equations for m N Theorem 5.1. The sequence m 0 = 1, m 1 = 1 2 , m 2 , . . . of moments defined by m n = 1 0 2(t) n dt (see [START_REF] Alkauskas | Explicit Series for the dyadic Period Function and Moments[END_REF]) satisfies the equalities

m n = 1 2 n ⌊n/2⌋ k=0 n 2k φ 2k (17)
where

φ n = ∞ k=0 n + k -1 k m n+k 2 n+k . ( 18
)
Remark 5.2. Since the increasing function

k -→ n+k-1 k 2 n+k 2 n+k+1 n+k k+1 = 2 k + 1 n + k
(for k > 0 and n a fixed natural integer) equals 1 for k = n -2 and since the moments m n are slowly decreasing, the main contribution to φ n comes asymptotically from summands with indices k roughly equal to n.

The main contribution to φ n is thus given by moments of the form m 2n+l with l an element of Z of small absolute value.

Similarly, the main contribution to m n in Formula (17) corresponds asymptotically to indices k ∼ n/4. and involves thus mainly moments of the form m n+l for l a small integer.

Theorem 5.1 is an immediate consequence of the following result. Proposition 5.3. For all n ∈ N we have the identities

1/2 0 2(t) n dt = 1 2 n+1 n k=0 n k (-1) k φ k and 1 1/2 2(t) n dt = 1 2 n+1 n k=0 n k φ k
with φ k defined by Formula (18).

Lemma 5.4. We have

φ n = 2 1 1/2 (22(t) -1) n dt . ( 19
)
for φ n defined by Formula (18).

Corollary 2.3 shows that Lemma 5.4 can be restated as

φ n = 1 0 |22(t) -1| n dt.
Proof of Lemma 5.4. Proposition 2.1 and the definition of Riemann sums show that we have

2 1 1/2 (22(t) -1) n dt = 2 lim l→∞ 1 2 l+1 2 l r=0 2 s(2 l + r) s(2 l+1 + 2 l + r) -1 n = lim l→∞ 1 2 l 2 l r=0 2s(2 l + r) -s(3 • 2 l + r) s(3 • 2 l + r) n .
Using (13) we get

2 1 1/2 (22(t) -1) n dt = lim l→∞ 1 2 l 2 l r=0 s(r) 2s(2 l + r) -s(r) n (20) or equivalently 2 1 1/2 (22(t) -1) n dt = lim l→∞ 1 2 l 2 l r=0 s(r) 2s(2 l + r) n   1 1 -s(r) 2s(2 l +r)   n .
Applying (10) we have

2 1 1/2 (22(t) -1) n dt = ∞ j=0 n + k -1 k m n+k 2 n+k
which ends the proof.

Proof of Proposition 5.3. Using Lemma 5.4 we have 4). This proves the first equality. The proof of the second equality is similar and left to the reader.

1 2 n+1 n k=0 n k (-1) k φ k = 1 2 n 1 1/2 n k=0 n k (1 -22(t)) k dt = 1 1/2 (1 -2(t)) n dt which equals 1/2 0 2(t) n dt by (

Spectral properties

Theorem 5.1 expresses the moment-vector (m 0 , m 1 , m 2 , . . . ) as a fixed point of a continuous linear operator T acting on the vector space l ∞ (R) of real bounded sequences. We study here a few spectral properties of T . They imply in particular uniqueness of the fixed point (m 0 , m 1 , . . . ) satisfying m 0 = 1.

We denote by

l ∞ = l ∞ (R) the real Banach space of bounded sequences with norm v ∞ = sup n∈N |v n | for v = (v 0 , v 1 , . . . ) in l ∞ . We set U = sup v∈l ∞ , v ∞ =1 U (v)
for the norm U of an endomorphism U ∈ End(l ∞ ). Similarly, we consider the norm

L = sup v∈l ∞ , v ∞ =1 |L(v)| of a continuous linear form L : l ∞ -→ R.
Formulae (17) and (18) suggest to consider the sequence of operators

v = (v 0 , v 1 , . . . ) -→ T n (v) = 1 2 n ⌊n/2⌋ k=0 n 2k ∞ l=0 2k + l -1 l v 2k+l 2 2k+l . ( 21
)
Proposition 5.5. Formula (21) defines continuous linear forms T 0 , T 1 , T 2 , . . . of norm T 0 = 1 and T n = 1 2 for n ≥ 1. We define an endomorphism T : l ∞ -→ l ∞ of the vector-space l ∞ by setting T = (T 0 , T 1 , T 2 , . . . ). Proposition 5.5 and T 0 (v 0 , v 1 , . . . ) = v 0 imply the following result:

Corollary 5.6. The restriction of the linear operator T = (T 0 , T 1 , T 2 , . . . ) to the subspace l ∞ 0 formed by all bounded sequences

(v 0 , v 1 , v 2 , . . . ) starting with v 0 = 0 yields an endomorphism of l ∞ 0 whose spectrum is contained in {z ∈ C | |z| ≤ 1 2 }.
In particular, the linear map

v -→ T (v) = (T 0 (v), T 1 (v), . . . )
defines a bounded linear operator of l ∞ which has a unique eigenvector of eigenvalue 1 of the form 1, 1 2 , . . . . The coordinates (m 0 , m 1 , . . . ) = 1, 1 2 , . . . of the unique eigenvector of eigenvalue 1 of T are of course the moments m n = 1 0 x n d?x of the density function associated to Minkowski's question-mark function ?.

Proof of Proposition 5.5. For v ∈ l ∞ such that v ∞ ≤ 1, we have |T n (v)| ≤ 1 2 n ⌊n/2⌋ k=0 n 2k 1 2 2k ∞ j=0 2k -1 + j j 1 2 j
with equality if and only if v is (up to a sign) the vector 1 = (1, 1, 1, . . . ) with all coefficients equal to 1. Applying (10) we have thus

T n = |T n (1)| = 1 2 n ⌊n/2⌋ k=0 n 2k 1 2 2k 1 1 -1 2 2k = 1 2 n ⌊n/2⌋ k=0 n 2k = 1 2 n (1 + 1) n + (1 -1) n 2 = 1 if n = 0 1 2 if n ≥ 1
which completes the proof.

Remark 5.7. Laplace's method shows that the coefficient

1 2 n ⌊n/2⌋ k=1 n 2k m -1 2k -1 1 2 m
of v m in T n given by Formula (21) is asymptotically equal to

1 2 1 2πnµ(1 + µ) ((1 + µ)/2) 1+µ µ µ n
for µ = m n having a bounded logarithm. This coefficient is asymptotically maximal for µ = 1 and decays exponentially fast otherwise. We have

lim n→∞ n ∞ 0 1 2 1 2πnµ(1 + µ) ((1 + µ)/2) 1+µ µ µ n dµ = 1 2
in agreement with Proposition 5.5.

Remark 5.8. The linear operator T has an unbounded eigenvector of eigenvalue 1 2 given by w = (0, 0, 2, 3, 4, 5, 6, 7, . . . ) as can be seen as follows: We have T 0 (w) = T 1 (w) = 0. For n ≥ 2, Formula (21) with w = (0, 0, 2, 3, 4, 5, 6, . . . ) boils down to

T n (w) = 1 2 n ⌊n/2⌋ k=1 n 2k ∞ l=0 2k + l -1 l 2k + l 2 2k+l .
Computing the derivative 2k

x 2k-1 (1-x) 2k+1 of x 1-x 2k at x = 1
2 either directly or using the series expansion (10) given by Lemma 4.1 we get the identity

4k = ∞ l=0 2k + l -1 l 2k + l 2 2k+l .
For n ≥ 2 we have thus

T n (w) = 1 2 n ⌊n/2⌋ k=0 n 2k 4k = 1 2 n ((1 + x) n + (1 -x) n ) ′ x=1 = n 2 .

Computational aspects

Theorem 5.1 is useful for computing numerical approximations of the first moments m 0 , m 1 , . . . , m N of Minkowski's question mark function. This can be done by computing an approximation ( m0 , m1 , . . . , mN ) of the unique attracting fixed point ( m0 , m1 , . . . ) of the form (1, . . . ) of the linear operator T • π N where π N : l ∞ -→ l ∞ is the projection defined by π N (x 0 , x 1 , . . . , x N , x N +1 , . . . ) = (x 0 , x 1 , . . . , x N , 0, 0, 0, . . . ).

The error

| mi -m i | is of order O(m N +1 ) = O N 1/4 e -2 √ N log 2 , see Formula (42).
Since the distance to the fixed point is essentially divided by 2 under each iteration of T • π N , the complexity of the resulting algorithm is roughly of order O N/ log 2N 2 if aiming at maximal accuracy. More precisely, the algorithm can be implemented as follows: m0 := 1, For n = 1, 2, 3, . . . , N do: mn := 0, End of loop over n, Iterate the following loop:

For n = 0, 2, 4, . . . , 2⌊N/2⌋ do: 1. Computations should be done over the real numbers with sufficient accuracy (maximal achievable accuracy is of order O(m N +1 ), see Section 10 for estimations).

b := 1 2 n , φn := 0, For k = 0,
2. The range and increment of the loop-variable n in line 060 is due to the fact that m 1 , . . . , m N depend only on φ 0 , φ 2 , φ 4 , . . . , φ 2⌊N/2⌋ in Formula (17).

3. Instructions 070 and 150 need a loop in many programming languages.

4. The variable b in line 070, 100, 110 corresponds to the factor n+k-1 k 1 2 n+k in Formula (18). 7. Using a known sequence of good approximations for m 1 , . . . , m N instead of 0 when initializing m1 , . . . , mN (instruction 030) decreases the number of useful (i.e. leading to significantly better precision) iterations for the outer loop.

8. A progressive increase of N (starting from some small initial value) during the iteration of the outer loop yields a small speedup.

Formulae of Alkauskas

Theorem 5.1 is based on Riemann sums for the integral

A = 2 1 1/2 (22(t) -1) n dt
obtained by subdividing the interval 1 2 , 1 into 2 l sub-intervals of equal length 1 2 l+1 . In this section we give a new proof of some formulae obtained by Alkauskas by considering the infinite subdivision

[0, 1] = {0} ∪ . . . 1 2 h , 1 2 h-1 ∪ 1 2 h-1 , 1 2 h-2 ∪ • • • ∪ 1 4 , 1 2 ∪ 1 2 , 1 1
suggested by the easy evaluations 2 1 2 h = 1 h+1 . Theorem 6.1. We have

m n = ∞ h=1 1 2 h 1 (h + 1) n ∞ k=0 k + n -1 n -1 m k (h + 1) k ( 22
)
and

m n = ∞ h=1 1 2 h 1 h n ∞ k=0 k + n -1 n -1 m k (-h) k . ( 23
)
Remark 6.2. From a computational point of view it is perhaps useful to rewrite the formulae of Theorem 6.1 as

m n = ∞ k=0 k + n -1 n -1 γ k+n m k ( 24
)
and

m n = ∞ k=0 k + n -1 n -1 (-1) k c k+n m k ( 25
)
where

γ n = ∞ k=1 1 2 k (k + 1) n = 2Li n 1 2 -1 and c n = ∞ k=1 1 2 k k n = Li n 1 2 where Li n (x) = ∞ k=1 x k
k n for x in the open complex unit-disc. Formula (22) (or (24)) should be preferred over (23) (or (25)). It converges faster (under iteration) and positivity of all coefficients ensures numerical stability.

Precomputing (and storing) the constants γ k and using (24) needs only twice as much memory but provides a significant speed-up.

Formula (25) has been used by Alkauskas for numerical computations of the first values of m n , see Appendix A3 of [START_REF] Alkauskas | Explicit Series for the dyadic Period Function and Moments[END_REF] or Proposition 5 of [START_REF] Alkauskas | The Moments of Minkowski Question Mark Function: The Dyadic Period Function[END_REF].

Since γ n ∼ 1 2 n+1 for large n, the arguments of Remark 5.2 show that the main contribution to m n in Formula (24) corresponds asymptotically to summands k ∼ n involving m n-a , . . . , m n+a . Proposition 6.3. Setting

I h (n) = 2 -h+1 2 -h 2(t) n dt . ( 26
)
we have

I h (n) = 1 2 h ∞ k=0 k + n -1 n -1 m k (h + 1) k+n (27)
and

I h (n) = 1 2 h ∞ k=0 k + n -1 n -1 (-1) k m k h k+n . ( 28
)
Lemma 6.4. We have

2 1 2 h + r 2 h+l = s(2 l + r) (h + 1)s(2 l + r) -s(r) (29)
and

2 1 2 h + r 2 h+l = s(2 l + r) hs(2 l + r) + s(2 l -r) (30) for 0 ≤ r ≤ 2 l . a b and 2 q + 1 2 h = c d
with (a, b) ∈ N 2 and (c, d) ∈ N 2 pairs of relatively prime natural numbers, then

2 q 2 h + r 2 h+l = as(2 l + r) + (c -a)s(r) bs(2 l + r) + (d -b)s(r) = cs(2 l + r) + (a -c)s(2 l -r) ds(2 l + r) + (b -d)s(2 l -r)
for l ∈ N and for r such that 0 ≤ r ≤ 2 l . One can then apply ( 14), ( 15), ( 16) (or a similar identity) with S = (2 l + r), s = s(r) in order to get Riemann sums for c/d a/b 2(t) n dt. Proof of Lemma 6.4. An induction on h establishes the formula for l = 0 (and r ∈ {0, 1}).

An induction on l (for constant h) ends the proof.

Proof of Proposition 6.3. We have

I h (n) = 1 2 h lim l→∞ 1 2 l 2 l r=0 2 1 2 h + r 2 h+l n .

By (29) we have

I h (n) = 1 2 h lim l→∞ 1 2 l 2 l r=0 s(2 l + r) (h + 1)s(2 l + r) -s(r) n = lim l→∞ 1 2 l+h 2 l r=0 1 (h + 1) n   1 1 - s(r) (h+1)s(2 l +r)   n

and (10) implies now

I h (n) = lim l→∞ 1 2 l+h 2 l r=0 1 (h + 1) n ∞ k=0 k + n -1 n -1 s(r) (h + 1)s(2 l + r) k = 1 2 h ∞ k=0 k + n -1 n -1 m k (h + 1) k+n .
This proves the first equality.

The second equality follows from (12) applied to (30) yielding the identities

I h (n) = 1 2 h lim l→∞ 1 2 l 2 l r=0 s(2 l + r) hs(2 l + r) + s(r) n = lim l→∞ 1 2 l+h 2 l r=0 1 h n   1 1 + s(r) hs(2 l +r)   n = 1 2 h ∞ k=0 k + n -1 n -1 (-1) k m k h k+n .
Proof of Theorem 6.1. Follows from m n = ∞ h=1 I h (n) where I h (n) is evaluated using Proposition 6. (ii) The series expansion of x -→ m x at x = 0 is given by

∞ n=0 x n n! ∞ k=n c n,k m k (31)
where

∞ k=n c n,k x k = (log(1 -x)) n . ( 32
)
Equivalently, the numbers c n,k are given by the equality

c n,k = (-1) k n! k! s(k, n) (33)
where the numbers s(k, m) defined by

k m=0 s(k, m)x m = x(x -1)(x - 2) • • • (x -k + 1)
are Stirling numbers of the first kind.

Remark 7.2. The rational numbers c n,k defined by (32) are given by the recursive formulae c 0,0 = 1, c 0,k = 0 if k > 0 and

c n+1,k = - k-1 j=1 c n,k-j j , n > 0 .
They are also defined by the equality

c n,k = (-1) n a 1 ,...,an≥1, a 1 +•••+an=k 1 a 1 • a 2 • • • a n .
Proof of Theorem 7.1. Extending formula (26) by considering

I h (x) = 2 -h+1 2 -h e x log(2(t)) dt
for arbitrary x ∈ C (where log(2(t)) ∈ R denotes the usual logarithm of the strictly positive real number 2(t)), the inequalities

1 h + 1 = 2(2 -h ) ≤ 2(t) ≤ 2(2 -h+1 ) = 1 h , t ∈ [2 -h , 2 -h+1 ] show |I h (x)| ≤ 1 2 h max t∈[ 1 1+h , 1 h ] |t x | ≤ (1 + h) |x| 2 h .
This implies

∞ h=1 I h (x) ≤ ∞ h=1 (1 + h) |x| 2 h < ∞ .
The map x -→ m x = ∞ h=1 I h (x) defines thus an entire function which coincides with m x for x ∈ N.

Using the symmetry 2(x) = 1 -2(x) we have

m x = lim l→∞ 1 2 l 2 l k=1 s(k) s(2 l + k) x = lim l→∞ 1 2 l 2 l -1 k=0 1 - s(k) s(2 l + k) x .
The n-th derivative of m x at x = 0 evaluates thus to

lim l→∞ 1 2 l 2 l -1 k=0 log 1 - s(k) s(2 l + k) n = lim l→∞ 1 2 l 2 l -1 k=0   - ∞ j=1 1 j s(k) s(2 l + k) j   n
which proves formula (31).

Remark 7.3. Holomorphicity of x -→ m x can also be proved using Proposition 3.3.

Two conjectural relations

The derivative of the holomorphic function x -→ m x (see Theorem 7. leading to the following conjectural identity.

Conjecture 8.1. We have

log 2 = ∞ n=1 m n 2n 1 + 1 2 n-1 . ( 34
)
A variation is given by Conjecture 8.2.

log 2 = ∞ n=1 m n n 1 2 n -(-1) n . ( 35
)

A third set of formulae

In this section we consider the partition

[0, 1] \ {1} = 0, 1 2 ∪ 1 2 , 3 4 ∪ 3 4 , 7 8 ∪ 7 8 , 15 16 ∪ . . . .
The resulting identities, well suited for computing asymptotics, are given by the following result:

Theorem 9.1.

m n = 1 2 ∞ j=0 n + j -1 j (-1) j m n+j + ∞ h=2 1 2 h h -1 h n n k=0 n k 1 h(h -1) k ∞ j=0 k -1 + j j (-1) j m k+j h j and m n = ∞ h=1 1 2 h h h + 1 n n k=0 n k -1 h(h + 1) k ∞ j=0 k -1 + j j m k+j (h + 1) j .
Remark 9.2. Only terms of order h ∼ n/ log 2 + O n 1/4 yield large contributions to the first sum of the formulae in Theorem 9.1. Corresponding terms of the second sum (over k) for such contributions decay exponentially fast. Terms of the third sum (over j) decay also exponentially fast for fixed h > 1 and for k small. We set

J h (n) = 1-2 -h 1-2 -h+1 2(t) n dt . ( 36
)
Proposition 9.3. We have for all h ∈ N, h ≥ 1 the identities

J h (n) = 1 2 h h -1 h n n k=0 n k 1 h(h -1) k ∞ j=0 k -1 + j j (-1) j m k+j h j (37)
and

J h (n) = 1 2 h h h + 1 n n k=0 n k -1 h(h + 1) k ∞ j=0 k -1 + j j m k+j (h + 1) j . ( 38
)
Observe that (37) boils down to

J 1 (n) = 1 2 ∞ j=0 n + j -1 j (-1) j m n+j (39)
for h = 1.

Proof of Proposition 9.3. Identity (11) of Proposition 4.4 implies

J h (n) = 2 -h+1 2 -h (1 -2(t)) n dt .
Using Formula (30) of Lemma 6.4 we get

J h (n) = 1 2 h lim l→∞ 1 2 l 2 l r=0 1 - s(2 l + r) hs(2 l + r) + s(2 l -r) n = 1 2 h lim l→∞ 1 2 l 2 l r=0 1 - s(2 l + r) hs(2 l + r) + s(r) n = lim l→∞ 1 2 h+l 2 l r=0 h -1 h + 1 h 2 s(r) s(2 l + r) + s(r) h n = lim l→∞ 1 2 h+l h -1 h n 2 l r=0 n k=0 n k 1 h k (h -1) k s(r) s(2 l + r) + 1 h s(r) k .
Using the identity

s(r) s(2 l + r) + s(r) h k = s(r) s(2 l + r) k   1 1 + 1 h s(r) s(2 l +r)   k = ∞ j=0 k -1 + j j (-1) j h j s(r) s(2 l + r) k+j
obtained by applying formula (10), we get the first equation.

Starting with

J h (n) = 1 2 h lim l→∞ 1 2 l 2 l r=0 1 - s(2 l + r) (h + 1)s(2 l + r) -s(r) n = lim l→∞ 1 2 h+l 2 l r=0 h h + 1 - 1 (h + 1) 2 s(r) s(2 l + r) -s(r) h+1 n = lim l→∞ 1 2 h+l h h + 1 n 2 l r=0 n k=0 n k (-1) k h k (h + 1) k s(r) s(2 l + r) -s(r) h+1 k .
and finishing as above yields the second identity.

Proof of Theorem 9.1. Follows from Proposition 9.3 applied to the obvious identity m n = ∞ h=1 J h (n).

Asymptotics

We set

λ = ∞ n=0 (log 2) n n! m n . (40)
Numerically, λ is approximately equal to 1.42815984554560290424313465212729430726822547802532544939052972 .

Theorem 10.1. For every strictly positive ǫ there exists a natural integer N such that

m n -λ ∞ h=2 1 2 h h -1 h n ≤ ǫ m n if n ≥ N .
The error given by the asymptotic approximation

m n ∼ λ ∞ h=2 1 2 h 1 - 1 h n (41)
in Theorem 10.1 is surprisingly small, see Section 10.3.

Corollary 10.2. We have

m n ∼ λ n 1/4 (log 2) 3/4 π 2 e -2 √ n log 2 (42)
for n → ∞.

Corollary 10.2 is of course equivalent to Theorem 1 in [START_REF] Alkauskas | An asymptotic Formula for the Moments of Minkowski Question Mark Function in the Interval[END_REF]. The constant λ defined by ( 40) is related to the constant

c 0 = 1 0 2 t 1 - 1 2 ?(t) dt = 1 log 2 - 1 2
1 0 2 t ?(t)dt in Theorem 1 of [3] by λ = c 0 2 log 2
and satisfies the following additional identities:

Proposition 10.3. We have

λ = 2 ∞ n=0 (-log 2) n n! m n = 4 3 ∞ n=0 (log 2) 2n (2n)! m 2n = 4 ∞ n=0 (log 2) 2n+1 (2n + 1)! m 2n+1 .
Observe that the constant λ appears also in the asymptotic expression λ n! (log 2) n+1 for m -n , see [START_REF] Alkauskas | The Moments of Minkowski Question Mark Function: The Dyadic Period Function[END_REF] or Proposition 11.8. Remark 10.4. A computation of λ with high precision needs only relatively few initial values of m 0 , m 1 , m 2 , . . . . I ignore however a direct approach for accurately computing only the first few values of m 2 , m 3 , m 4 , . . . . Proposition 10.5. We have

lim n→∞ n 1/4 (log 2) 3/4 π 2 e -2 √ n log 2 -1 ∞ h=2 1 2 h 1 - 1 h n = 1 .
Proof of Proposition 10.5. We apply Laplace's method to ∞ h=2 1

2 h 1 -1 h n .
The derivative

f ′ n (x) = 1 2 x 1 - 1 x n (n + x(1 -x) log 2) x(x -1) of the function f n (x) = 1 2 x 1 -1
x n has roots given by the solutions of

x 2 -x = n log 2 .
Assuming x real and positive, the positive root of f ′ n is given by

ρ = 1 + 1 + 4n/ log 2 2 = n log 2 + 1 2 + 1 8 log 2 n + O 1 √ n 3
and we have

f n (ρ) = 1 √ 2 e -2 √ n log 2 1 + O 1 √ n .
A straightforward computation shows

f ′′ n (ρ) = 1 √ 2 e -2 √ n log 2 -2 √ log 2 3 √ n + O 1 n . ( 43
) Applying Laplace's method ∞ 2 f n (h)dh ∼ f n (ρ) ∞ -∞ e - f ′′ n (ρ) fn(ρ) t 2 /2 dt = 2πf n (ρ) 3 -f ′′ n (ρ)
to the integral approximation

∞ 2 f n (h)dh of ∞ h=2 f n (h)
we get the result.

Proposition 10.6. For every ǫ > 0 there exists a natural integer A such that

0 ≤ m n - ⌊ √ n/ log 2+An 1/4 ⌋ h∈⌊ √ n/ log 2-An 1/4 ⌋ J h (n) < ǫm n for all n large enough with J h (n) = 1-2 -h
1-2 -h+1 2(t) n dt given by (36).

Proof. The easy evaluation 2 1 -

1 2 h = 1 -1 h+1 for h ∈ N shows 1 - 1 h ≤ 2(t) ≤ 1 - 1 h + 1 for t ∈ 1 -1 2 h-1 , 1 -1 2 h and we have 1 2 h 1 - 1 h x ≤ J h (x) ≤ 1 2 h 1 - 1 h + 1 x for real positive x. Since the unique positive root of the logarithmic deriva- tive df /dh f = -log 2 + x h(h -1) with respect to h of f = 1 2 h 1 -1 h
x is given by h ∼ x/ log 2 for large x, the decay of the function

s -→ 1 2 √ x/ log 2+sx 1/4
1 -1

x/ log 2 + sx 1/4

x is exponentially fast in |s| for large x. This implies the result.

Proof of Theorem 10.1. Setting

Jh (n) = 2 h h h -1 n J h (n) formula (37) of Proposition 9.3 shows the identities Jh (n) = n k=0 n k 1 h k (h -1) k ∞ j=0 k -1 + j j (-1) j m k+j h j = n k=0 (log 2) k k! k-1 j=1 1 -j n h(h-1) n log 2 k ∞ j=0 k -1 + j j (-1) j m k+j h j .
For k fixed and for h = n/2 log 2 + O(n 1/4 ) we have

lim n→∞ k-1 j=1 1 -j n h(h-1) n log 2 k = 1
and we get the asymptotics

Jh (n) ∼ ∞ k=0 (log 2) k k! m k = λ for h = n/ log 2 + O n 1/4 . Proposition 10.6 shows now m n ∼ ǫ ⌊ √ n/ log 2+An 1/4 ⌋ h=⌊ √ n/ log 2-An 1/4 ⌋ J h (n) ∼ ǫ ⌊ √ n/ log 2+An 1/4 ⌋ h=⌊ √ n/ log 2-An 1/4 ⌋ 1 2 h h -1 h n Jh (n) ∼ ǫ λ ∞ h=2 1 2 h h -1 h n
for n → ∞ and fixed A (depending on ǫ) with a ∼ ǫ b denoting |a -b| < ǫa for arbitrary small ǫ if n is large enough.

Proof of Proposition 10.3. Working with formula (38) we get the asymptotics

m n ∼ ∞ h=1 1 2 h h h + 1 n ∞ k=0 (-log 2) k k! m k = 2 ∞ k=2 1 2 h h -1 h n ∞ k=0 (-log 2) k k! m k
which imply the first equality by comparing with Theorem 10.1. The two other identities are easy consequences.

Proof of Corollary 10.2. Follows from Theorem 10.1 and Proposition 10.5.

Asymptotic formula for φ n

Using similar techniques, we get the asymptotic approximation

φ n ∼ 2λ ∞ h=3 1 2 h 1 - 2 h n (44)
(where λ is given by ( 40)) for φ n = 2 Using Laplace's method for the right side of (44) we get the simpler and less accurate expression

φ n ∼ λ (2n) 1/4 √ π log(2) 3/4 e -2 √ 2n log 2 . ( 45
)

A second asymptotic formula

The motivation for this section is the estimation of the order of the error in the asymptotic approximation (41).

A refinement of the Riemann sum underlying Formula (41) should yield a slightly more accurate approximation for m n . The order of the difference between the two formulae should be a measure for the accuracy of (41).

We subdivide the interval underlying the integral J h (n) defined by (36) into two intervals of equal lengths. We have

J h (n) = A h (n) + B h (n) where A h (n) = 1-3•2 -h-1 1-2 -h+1 2(t) n dt and B h (n) = 1-2 -h 1-3•2 -h-1 2(t) n dt .
We have

A h (n) = 1 2 h+1 lim l→∞ 1 2 l 2 l r=0 1 - s(2 l + r) + s(r) hs(2 l + r) + (h + 1)s(r) n = 1 2 h+1 lim l→∞ 1 2 l 2 l r=0 2h -1 2h + 1 - s(r) (2h + 1) 2 (s(2 l + r) -h+1 2h+1 s(r)) n = 1 2 h+1 2h -1 2h + 1 n n k=0 n k (-1) k (4h 2 -1) k lim l→∞ 2 k 2 l 2 l r=0 s(r) 2s(2 l + r) -2h+2 2h+1 s(r) k which yields lim h→∞ A h (n) = 1 2 h+1 2h -1 2h + 1 n n k=0 n k (-1) k (4h 2 -1) k 2 k φ k by Identity (20).
For h = n/ log 2 + O(n 1/4 ) we have thus

A h (n) ∼ 1 2 h+1 2h -1 2h + 1 n ∞ k=0 (-log 2) k 2 k k! φ k .
A similar calculation shows

B h (n) ∼ 1 2 h+1 2h -1 2h + 1 n ∞ k=0 (log 2) k 2 k k! φ k for h = n/ log 2 + O(n 1/4 ).
We get thus for large n and h = n/ log 2 + O(n 1/4 ) the approximation

J h (n) ∼ 1 2 h ∞ k=0 (log 2) 2k 2 2k (2k)! φ 2k . Setting ρ = ∞ k=0 (log 2) 2k 2 2k (2k)! φ 2k (46)
we have asymptotically

m n ∼ ρ ∞ h=1 1 2 h 1 - 2 2h + 1 n .
Using Laplace's method we get the asymptotic approximation

∞ h=1 1 2 h 1 - 2 2h + 1 n ∼ n 1/4 √ π (log 2) 3/4 e -2 √ n log 2 .
This shows

m n ∼ ρ n 1/4 √ π (log 2) 3/4 e -2 √ n log 2 (47)
and implies the identity

ρ = λ √ 2 (48)
as can be seen by comparing the two asymptotic approximations (42) and (47) of m n .

The asymptotic formula

m n ∼ λ ∞ h=1 1 2 h+1/2 1 - 1 h + 1/2 n (49)
should thus be slightly better than (41), see Figure 1 in Section 10.3.

An estimation for the error of the asymptotic formulae

Setting x -→ S x (n) = ∞ h=1 1 2 h+x 1 - 1 h + x n , (50)
the asymptotic formulae (41) and (49) can be rewritten as m n ∼ λS 0 (n) and m n ∼ λS 1/2 (n). Since x -→ S x (n) is almost 1-periodic (for small positive x and huge fixed n) and oscillates experimentally around the exact value of the integral

S (n) = ∞ 1 1 2 t 1 - 1 t n dt, (51)
it is tempting to rescale the errors m n -S x (n) by the inverse of the factor

κ(n) = S 0 (n) -S (n) 2 + S 1/4 (n) -S (n) 2 (52)
given by the "amplitude" of the almost 1-periodic function x -→ S x (n) -S (n). The sequence S (n) of integrals is easy to compute recursively: We have the initial values

S (0) = ∞ 1 dt 2 t = 1 2 log 2 S (1) = ∞ 1 1 2 t 1 - 1 t dt = 1 2 log 2 + -log 2 -∞ e t t dt? = 1 2 log 2 - ∞ log 2
e -t t dt?

= 1 2 log 2 + Ei(-log 2) (where Ei(x) = x -∞ e t t dt = - ∞ -x e -t
t dt is the exponential integral) and integration by parts yields the recursion relation

S (n) = 2 + log 2 n -1 S (n -1) -S (n -2). (53)
The normalized errors

E 0 (n) = = 1 κ(n) m n -λ ∞ h=2 1 2 h 1 - 1 h n , (54)
E 1/2 (n) = 1 κ(n) m n -λ ∞ h=1 1 2 h+1/2 1 - 1 h + 1/2 n , (55)
E (n) = 1 κ(n) m n -λ ∞ 1 1 2 t 1 - 1 t n dt (56)
are depicted in Figure 1

O(κ(n)).
Remark 10.7. The existence of the linear recurrence relation (53) implies the existence of asymptotic recurrence relations (given by the same formula) for the sequences m n and S x (n).

The asymptotic linear recurrence formula for m n can be improved into an affine asymptotic formula using ideas of the next Section.

Remark 10.8. It would be interesting to understand the asymptotic behaviour of the amplitude κ(n) given by Formula (52). (The number κ(n) is n . The accuracy of the asymptotic formulae m n ∼ λS * (n) (for * = 0, 1/2 and ) is thus surprisingly high.

Increasing accuracy

The behaviour of the error-terms E * (n) occurring in the previous Section suggests to try an asymptotic formula of the form with κ(n) given by Formula (52).

m n ∼ λS (n) + a S 0 (n) -S (n) + b S 1/4 (n) -S (n) ( 57

An improved algorithm

Accurate asymptotic approximations can be used for improving the algorithm given in Section 5.2. Indeed, the cutoff at N induces large relative errors for the last values of φn . It is thus natural to compute φ0 , φ2 , . . . , φ2⌊N/2⌋ using the first N + 1 values m0 , . . . , mN and M -N additional values mN+1 , . . . , mM given by asymptotic approximations of m N +1 , . . . , m M (for M > N a suitable integer depending on N and on the accuracy of the chosen approximation). We illustrate this by modifying the algorithm of Section 5.2 using highlevel instructions in order to involve the asymptotic approximation (41) (the approximation (42) is of much lesser interest):

Add the lines 005 Precompute (and store) sufficiently accurate values S(n) of S 0 (n) (or, slightly better, of S (n)) for n = N + 1, . . . , M . For k = 0, 1, 2, . . . , M -n do: The resulting algorithm can easily be modified in order to work with other asymptotic approximations. The author used mainly (57) (this needs precomputations of approximations for S (n), S 0 (n), S 1/4 (n) with n in {N + 1, . . . , M }).

Concerns using an algorithm based on a conjectural formula can be avoided by checking the final data using a single iteration of (the main loop in) the original algorithm (described in Section 5.2) with a sufficiently high value N ′ > N (with missing values replaced by their (conjecturally very accurate) approximations). The obtained data are exact up to an absolute error bounded by max(|ǫ|, m N ′ +1 ) with ǫ denoting the maximal modification of m1 , . . . , mN ′ during the final checking-run.

The improved version has smaller memory requirement and a much better running time : The (conjectural) accuracy of the used approximation should more than double the number of achievable correct digits for a given value of N . In order to achieve the same accuracy, the original algorithm has to be run with N multiplied by more than 4 which multiplies the running time of the main loop by more than 16 = 4 2 .

1 -2 1 2 -4 1 -2 6 -6 1 2 -8 12 -8 1      
and their coefficients are described by the following result.

Proposition 11.3. Let σ n , n ∈ Z be a sequence (with values in a commutative ring containing 1) indexed by the set Z of all integers such that

σ -n -σ n = n-1 k=0 n k (σ -k + σ k ) . Then σ -i = i j=0 α i,j σ j σ i = i j=0 β i,j σ -j
for all i ∈ N where α i,j , β i,j , 0 ≤ i, j are integers given by the formulae

α i,j = i j ∞ h=1 h i-j 2 h (59)
and

β i,j = 1 if i = j 2(-1) i+j i j otherwise.
In particular, the matrices A and B with coefficients α i,j , β i,j , 0 ≤ i, j are mutually inverse lower triangular unipotent integral matrices. Proof. We have α i,i = 1 as required and the matrix A is clearly lower triangular. The proof is now by induction on the row-index i of the coefficients α i,j for A. Equation (58) of Proposition 11.1 shows that we have

α i+1,j = i l=0 i + 1 l (α l,j + δ l,j )
for i + 1 ≥ j, where δ l,j = 1 if l = j and δ l,j = 0 otherwise. We get

α i+1,j = i + 1 j - i + 1 i + 1 i + 1 j ∞ h=1 h i+1-j 2 h + ∞ h=1 i+1 k=0 i + 1 k k j h k-j 2 h = i + 1 j - i + 1 j ∞ h=1 h i+1-j 2 h + ∞ h=1 i+1 j 2 h i+1 k=0 i + 1 -j k -j h k-j = i + 1 j 1 - ∞ h=1 h i+1-j 2 h + ∞ h=1 (h + 1) i+1-j 2 h = i + 1 j ∞ h=1 h i+1-j 2 h .
This implies the formula for the coefficients of A.

We prove the formula for the coefficients of the inverse matrix B = A -1 by computing the product AB. We have

i k=j α i,k β k,j = 2 i k=j α i,k (-1) k+j k j -α i,j = 2 ∞ h=1 i k=j h i-k 2 h i k k j (-1) k+j -α i,j = ∞ h=1 (-1) j h i 2 h-1 i k=j i k k j 1 (-h) k -α i,j . Identity 4.3 of Lemma 4.3 shows that this simplifies to ∞ h=1 (h -1) i-j 2 h-1 i j -α i,j .
This equals 1 if i = j and 0 for i > j by definition of α i,j .

The sum appearing in (59) defines natural integers having a recursive definition: for n ≥ 1.

The sequence of integers γ 0 , γ 1 , . . . starts as 1, 2, 6, 26, 150, 1082, 9366, 94586, 1091670, . . . , see sequence A629 of [START_REF]On-Line Encyclopedia of Integer Sequences[END_REF].

Proof of Proposition 11.4. We have

γ n = 1 2 + 1 2 ∞ h=1 (h + 1) n 2 h = 1 2 + 1 2 n j=0 n j ∞ h=1 h n 2 h = 1 2 + 1 2 n j=0 n j γ j
which implies the result.

Remark 11.5. Lower triangular matrices with lower triangular coefficients γ i,j of the form i j c i-j for some sequence c 0 , c 1 , . . . form a commutative algebra. Indeed, the map associating to such a matrix with coefficients i j c i-j the formal exponential power series ∞ n=0 c n x n n! defines an isomorphism of algebras onto the algebra of formal exponential power series (with product given by the obvious "bilinear"extension of Using the easy evaluation m 0 = 1, m 1 = 1 2 , the case n = 1 yields the nice evaluation

∞ j=0 m j = 5 2 (63)
which can be used as an accuracy-check for numerical computations. Similarly, using n = 2, we get the identity m 2 + 8 = ∞ j=0 (j + 1)m n . Subtraction of (63) yields k! m k given by (40). The following easy result is probably well-known: Lemma 11.9. We have

lim n→∞ (log 2) n+1 n! ∞ k=1 k n 2 k = 1 .
Proof of Lemma 11.9. We apply Laplace's method to with λ given by (40).

a b and 2 m+1 2 n

 2 = c d where a, b, respectively c, d, are coprime natural numbers. The values 2(m/16) for m = 0, . . . , 16 are: Values of 2 for arguments in D are easy to compute as follows: We define the Stern-sequence s(0), s(1), s(2), . . . recursively by s(0) = 0, s(1) = 1, s(2n) = s(n) and s(2n + 1) = s(n) + s(n + 1). Its first coefficients are given by

  with a, b and c, d pairs of coprime natural numbers). In particular, 2 extends to a strictly increasing continuous function (still denoted) 2

  1, 2, . . . , N -n do: φn := φn + b mn+k , b := n+k 2(k+1) b, End of loop over k, End of loop over n, For n = 1, 2, 3, . . . , N do: b := 1 2 n , mn := 0, For k = 0, 1, 2, . . . , ⌊N/2⌋ do: mn := mn + b φ2k , b := (n-2k-1)(n-2k) (2k+1)(2k+2) b, End of loop over k, End of loop over n, End of outer loop (starting at 050). Comments:

5 .

 5 The variable b in line 150, 180,190 corresponds to the factor 1 2 n n 2k in Formula (17). 6. Maximal possible accuracy is achieved by iterating the outer loop (instructions 060-210) roughly 2 N/ log 2 times, see Corollary 10.2.

3 .7

 3 Holomorphicity of m x Theorem 7.1. (i) The map n -→ m n extends to an entire function x -→ m x .

1 1/ 2

 12 (22(t) -1) n dt, see Formula (19) in Lemma 5.4. The relative error seems again to be of order O φ 5/4 n and has again (suitably normalized) a more or less periodic behaviour as a function of √ n.

Figure 1 : 2 √ n log 2 which

 122 Figure 1: Error of asymptotical formulae

  ) with λ defined by (40) and S * (n) as in the previous Section. Experimentally, such a formula seems to exist with a ∼ -.521901056340432536774725873446, b ∼ -.148755851763595338634628933193.The term λS (n) is of course the principal contribution and plays the role of Formula (41) or (49). The two remaining terms a S 0 (n) -S (n) and b S 1/4 (n) -S (n) sum up to a fairly regular (damped) oscillatory contribution of much lesser size. More precisely, its local amplitude should be asymptotically equal to λ √ a 2 +b 2 κ(n)

  λ S(n) for n = N + 1, . . . , M . at the obvious locations. Replace 090 by 090

Proposition 11. 4 .

 4 The natural integersγ n = ∞ h=1 h n 2 h(appearing in (59)) have the recursive definition γ 0 = 1 andγ n = 1 +

(

  with γ n defined by Proposition 11.4) and m n = m -n + 2 for all n in N. Corollary 11.6 is better suited than Proposition 3.3 for computing values m -N using m N . It involves only finitely many terms of m N with coefficients which are decreasing. (The main contribution to m -n given by the formula of Proposition 3.3 corresponds to summands indexed by integers close to n 2 log 2 .)Combining Formula (60) of Corollary 11.6 with Proposition 3.3 we get:Corollary 11.7. We have for all n in N the identity 1)m j ,26m 0 + 18m 1 + 6m 2 + m 3 = 150m 0 + 104m 1 + 36m 2 + 8m 3 + m 4 =

∞ 1 x 2 n n log 2 ne 2 ne(log 2 )

 12222 n 2 -x dx ∼ ∞ k=1 k n 2 -k . The derivative d dx x n e -x log 2 = n x -log 2 x n e -x log 2of x n 2 -x has a unique strictly positive root at n log 2 and second derivative -(log 2) -n at the critical point x = n log 2 corresponding to the maximum n log -n of the function x -→ x n 2 -x . Laplace's method yields thus the asymptotics n+1 where the last asymptotic equivalence follows from Stirling's formula n! ∼ √ 2πn n n e n .Proof of Proposition 11.8. Using Corollary 11.6 and the asymptotics ∞ n+1 given by Lemma 11.9, we get the asymptotics m

  (n) for n in {100, . . . , 400}. Points on the smallest sinusoidal curve are associated to E , points on the sinusoidal curve of intermediate size to E 1/2 and points on the largest curve to E 0 . In all three cases the error seems to be close to a damped periodic function of √ n of local amplitude

	and	√ n, E	representing the points (	√ n, E 0 (n)) ,	√ n, E 1/2 (n)

holds for n ∈ N a natural integer.

Remark 11.2. The generalization

of Proposition 11.1 fails for arbitrary complex values of z. Indeed, Proposition 11.1 is based on the identity

12 Geometric means for the Stern sequence

It is an easy exercise to compute the arithmetic mean 1

j=2 n s(j). The following result gives asymptotics for the geometric mean: Theorem 12.1. There exists a real constant β such that

Remark 12.2. The constant α is involved in the Hausdorff dimension of growth points for ?(x), see Kinney or Alkauskas. See also Conjecture 8.1 for a conjectural manifestation of α.

I am not aware of the existence of an efficient method for computing the value of β ∼ -.0851895 with high precision.

Lemma 12.3. Given an increasing function ϕ : [0, 1] -→ [0, 1] and a strictly positive natural integer N we have

Proof. The error of the trapezoidal rule

Proof of Theorem 12.1. We consider

where the second identity follows from the evaluations s(2 n ) = s(2 n+1 ) = 1. Using (12) we get

and (13) yields

This proves the existence of β.


Sean Thorpe
email: thorpe.sean@gmail.com

Indrajit Ray
email: indrajit@cs.colostate.edu

Tyrone Grandison
email: tgrandison@proficiencylabs.com

Abbie Barbir
email: abbie.barbir@bankofamerica.com

Robert France
email: france@cs.colostate.edu

Hypervisor Event Logs as a Source of Consistent Virtual Machine Evidence for Forensic Cloud Investigations

Cloud Computing is an emerging model of computing where users can leverage the computing infrastructure as a service stack or commodity. The security and privacy concerns of this infrastructure arising from the large co-location of tenants are, however, significant and pose considerable challenges in its widespread deployment. The current work addresses one aspect of the security problem by facilitating forensic investigations to determine if these virtual tenant spaces were maliciously violated by other tenants. It presents the design, application and limitations of a software prototype called the Virtual Machine (VM) Log Auditor that helps in detecting inconsistencies within the activity timelines for a VM history. A discussion on modeling a consistent approach is also provided.

Introduction

Temporal event logs meticulously record events that have occurred in the history of the computer system, and therefore, constitute a valuable source of digital evidence. Event logs are generated by the operating system as well as by other subsystems and their applications. There has been a significant amount of research about the examination and the auditing of such logs for post incident forensic purposes [START_REF] Rodgers | The role of criminal profiling in the computer forensics process[END_REF][START_REF] Rodgers | Log auditing through model checking[END_REF]. With cloud computing service environments, the expectations for post incident forensics is no different. Cloud computing is predicated on the well known service oriented architecture (SOA) and harnesses the power of the virtualization stack. The known services offered across the virtual stack layers are Infrastructure as Service (IAAS), Platform as a Service (PAAS) and Software as a Service (SAAS). In our work the PAAS provision, which handles the hypervisor logs, is our primary concern. By studying the hypervisor logs, this work represents the first body of work in the literature that seeks to explore closing the semantic gap of how eye witness forensic data that can be collected between the lower layers and higher virtualization layers and is motivated by prior work [START_REF] Rodgers | The role of criminal profiling in the computer forensics process[END_REF][START_REF] Rodgers | Log auditing through model checking[END_REF][START_REF] Srinivas | Trail of Bytes: Efficient support for Forensic Analysis[END_REF].

In this work the log categorization used is the hypervisor event logs, which contains a hierarchy of application logs, security logs, error logs and system logs. Some have likened a log file in computer forensics to an eyewitness in a traditional crime scene [START_REF] Rodgers | The role of criminal profiling in the computer forensics process[END_REF]. The analogy seems befitting when using the hypervisor logs to manage virtual crime scenes for which the multi-tenant VMs are all co-located.

Providing a picture of what happened through the analysis of the hypervisor event logs at a virtual crime scene is no trivial task. Detecting patterns that may be events of interest by hand in a large log file is not feasible. Managing the sheer volume of log data is a well known quantity problem. Logs must be parsed programmatically and even this can take a very long time, with the exact amount of time varying significantly, and is often dependent on the type of algorithm employed to detect the patterns of interest [START_REF] Rodgers | Log auditing through model checking[END_REF].

As log data are explicitly a record of events, establishing their reliability is of particular importance. Log files are written to very frequently and hence may get corrupted or could be difficult to understand; as records may be saved in an unexpected sequence as a result of unusual system behavior, e.g. software bug or power outage. As log files are an obvious record of events, they are also an obvious target for tampering. Suspicious events indicating that something is wrong may be deliberately removed, rendering all or a part of the log potentially fraudulent.

Our work addresses the issue of deliberate tampering, internal contradictions and inconsistent entries with these hypervisor event logs within the storage area network (SAN) data centre environments. We attempt to improve on the state of the art by providing a forensic platform that transparently monitors and records data access events using these PAAS logs as a form of static snapshot state analysis for a post incident VM cloud investigation. This approach complements the traditional statistical trace analysis methods and the VM memory introspection methods established in prior work [START_REF] Srinivas | Trail of Bytes: Efficient support for Forensic Analysis[END_REF][START_REF] Gidwani | A Comprehensive Survey of Event Analytics[END_REF][START_REF] Pauw | Visual and algorithmic tooling for system trace analysis: A case study[END_REF]. As it relates to using the PAAS logs to detect VM attacks, particularly session hijacking, this represents independent ongoing work using several data mining techniques [START_REF] Thorpe | A Model for Compiling Truthful Forensic Evidence from the Log Cloud Hypervisor Databases[END_REF][START_REF] Thorpe | Log Audit Explanation Templates with Private Data Clouds[END_REF] that unearth ground truth forensic evidence based on anomalous patterns detected from such logs. As it is now, the timestamps recorded in the hypervisor event logs may be unreliable, as result of both flaws in the clocks that generate them and the nature of the software that records entries to these data cloud logs.

The rest of this paper is organized as follows. Section 2 introduces our VM profiling model. Section 3 examines approaches for the detection of inconsistency in timelines, dealing both with inconsistencies in VM event timestamps and VM events omitted from the hypervisor kernel system's record. Section 4 describes the experiments with the tool for testing the approaches discussed in Section 3. Section 5 describes the rule base for the experiments and evaluates the detection techniques based on the rule base. Section 6 provides a formal discussion on constructing the consistency approach, and Section 7 provides the discussion of the experimental results. Section 8 presents a discussion of future work, Section 9 provides the related work and we conclude in Section 10. This work is based on concepts from the computer-profiling model described by Marrington et al. [START_REF] Marrington | A Model for Computer Profiling[END_REF]. The authors' model of a computer system consists of objects representing the various entities that form part of the computer system's operation. These entities include users, data files, system software, hardware devices, and applications. The objects discovered on the computer system under examination, collectively referred to as the set O, are classified according to their type. In their model [START_REF] Marrington | A Model for Computer Profiling[END_REF], there are four broad types of objects (Application, Principal, Content and System) with increasingly specific subtypes.

We adopt in our work each of these categories as VM sets. The set of Application objects, A, consists of all the application software on the VM host computer system. The set of Principal objects, P, consists of all the computer system's users and groups, and all of the people and organizations otherwise discovered in the examination of the computer system. Of these objects, some Principal objects are described as canonical if they represent definite entities on the computer system that are actors in their own right, such as users and groups. Principal objects may be described as non-canonical if they represent people or groups of people who may not be actors on the system, but may be, for instance, people mentioned in documents. The set of Content objects, C, consists of all the documents, images and other data files on the host computer system from which the VMs are running. The set of VM System objects, S, consists of all the VM configuration information, system software and hardware devices on the VM host computer system. A, S, C, and P are subsets of O, the set of objects on the cloud system under investigation.

We characterize our model with the set of all times in the history of the VM host computer system, T v , and the set of all events, Evt, which have taken place in the history of the VM host computer system. Let t be a time in T v , x be the VM object that triggered the VM event, y be the object that was the target of the event, 𝜀 describe the action of the event, and 𝛼 describe the result of the event (successful, unsuccessful, or unknown). An event evt in the set Evt consists of the quintuple evt = t, x ∈ O, y ∈ O,ε,α

(

) .

This same finite set Evt consists of two enumerable subsets, and one subset which cannot be enumerated. The first subset -the recorded events set EvtR -consists of VM events that are recorded in the VM host computer hypervisor system's logs. The second subset -the inferred events set EvtI -consists of events that are not recorded in logs, but that can be inferred on the basis of other digital evidence on the system, such as relationships between different objects. These two sets do not necessarily describe the complete history of the cloud system in an exhaustive manner. There may be other events that took place and were unrecorded and left no artifact from which they could be inferred. These VM events are obviously unknown, and comprise the final subset of Evt.

The set EvtI is particularly vulnerable to inconsistency or incompleteness in the data obtained from the VM target computer's file system. Contradictory, inaccurate or missing information can lead to an incomplete timeline of a user's activity. EvtR is a direct representation of the contents of the VM host hypervisor system's logs, and consequently, incorporates any inaccurate event records in the system logs. Further, if a VM event is not logged, and cannot be inferred, it will not be an element of either EvtR or EvtI. Handling unknown events within the VM history of the computer system is a challenge and hence the less accurate the timeline of the target computer's activity will be. We address this challenge in an independent paper. For this work, we focus on the declared events and making the inferences from these stated events. This work provides a means for the semiautomated detection of inaccuracy or incompleteness leading to chronological inconsistency in timelines of VM computer activity.

Marrington et al. [START_REF] Gladyshev | Formalizing event time bounding in digital investigations[END_REF], discussed a timestamp-based technique for building a timeline about a given object in the profile of the computer system. However, their approach is not resilient to inaccuracies in timestamps, which may cause VM events to appear out of sequence. Missing events, whether removed manually or simply never recorded, lead to timelines that may present events out of the context they actually occurred. We posit that as a general principle, the failure to detect an inconsistency in a timeline is a greater problem for the purposes of VM activity time-lining than falsely identifying an event as inconsistent. This is simply because false positives can be manually investigated and dismissed, whereas false negatives will never receive further attention. Nevertheless, it is obviously desirable to minimize the rate of false positives in all detection techniques.

A limitation of any time-lining activity based on timestamps provided by a computer's system clock is the inaccuracy inherent in such clocks. This inaccuracy in computergenerated timestamps is normal, and the solution suggested most frequently in the literature is to note the system clock time of a computer under investigation at the time of its examination and to determine the discrepancy between that time and the time of a reference clock [START_REF] Rodgers | The role of criminal profiling in the computer forensics process[END_REF][START_REF] Marrington | Event-based computer profiling for the forensic reconstruction of computer activity[END_REF]. However, this solution does not address the issue of clock skew. A few works, notably [START_REF] Rodgers | Log auditing through model checking[END_REF][START_REF] Nolan | First responder's guide to computer forensics[END_REF], propose algebra for the formal expression of falsifiable hypotheses about the discrepancy between a computer's clock and physical time. The term proposed for such a phenomenon is a clock hypothesis. In practice, it would be necessary to form a clock hypothesis for every moment in time throughout the history of the VM host system. Our tool is intended to detect internal inconsistency in timelines. An investigator could potentially be assisted in the formation of VM clock hypotheses using the output of our tool.

VM Log Auditor for Timelines

We now describe the approaches employed by our log auditor software to detect inconsistency in timelines. Inconsistency in virtual machine computer activity timelines can arise because hypervisor kernel log events in the timeline are out of sequence, or VM events that should be in the timeline are missing.

Detecting out of Sequence VM Timelines

There are some VM events that need to occur before some other event can happen. This sort of relation between events is described as the happened-before relation [START_REF] Buchholz | A brief study of time[END_REF]. Gladyshev and Patel [START_REF] Fidge | Logical time in distributed computing systems[END_REF] discuss the application of the happened-before relation to a forensic context. An example of such a relation between two events would be that a VM user x must "login" successfully to the computer system before the user x can "execute" the application y. So the happened-before (→) relation implies that in the VM activity timeline, the time of the VM login event must be before the time of the execution event. We express this as follows. Let x ∈ P, y ∈ 𝑨, and t m, t n ∈ T y . Then ((t m , x, y, login, success) → (t n , x, VM system, execution , success )) ⇒ (t m > t n ), where ⇒ is the logical implication operator . Note that the happened-before relation is transitive [START_REF] Buchholz | A brief study of time[END_REF][START_REF] Fidge | Logical time in distributed computing systems[END_REF]:

After the construction of a VM log timeline (which is a sequence over the set Evt) in the log auditor's execution process, an evaluation can be applied to all VM events ordered by their timestamp. If a VM event vmevt a has a happened-before relation to vmevt b , but the VM kernel log timestamp (t b ) of vmevt b suggests that vmevt b occurred before vmevt a then we can say that t a and t b are inconsistent. In order to detect this inconsistency, a rule base must be created which describes the happened-before relations for the various types of events [START_REF] Thorpe | A Formal Temporal Log Model for the synchronized Virtual Machine Environment[END_REF]. When the VM timeline is evaluated against the rules base, the inconsistent events can be identified and assertions about their time stamps can be made.

Consider the two rules vmevt a → vmevt b and vmevt b → vmevt c with vmevt a = t a ∈T y , x, system, login, success ( )

vmevt b = t b ∈T y , x, a, execute, α ∈ success, fail, unknown { } ( ) vmevt c = t c ∈T y , x, system, logout, success ( )
where x is a User VM object, a is an Application VM objects, and system is a VM System object representing the target VM computer system itself. Then, by the transitivity property of the happened-before relation,

vmevt a → vmevt b ( ) ∧ vmevt b → vmevt c ( ) ( ) ⇒ vmevt a → vmevt c ( )
For the purposes of this example, let the time-lining function VH x ( ) produce a timeline (where a timeline is an ordered set of discrete time instances) corresponding to a single VM user session of the user x. The first rule states that a user x must be logged in before executing any application. The second rule states that user x cannot have logged out before performing that execution. If the execution event vmevt b occurs, the login event vmevt a must happen before it, and vmevt b must happen before the logout event vmevt c . Therefore, the physical time t c at which the event vmevt c must have occurred must be after the physical time t b at which the event vmevt b must have occurred, which must in turn be after the physical time t a at which the event vmevt a must have occurred.

This is stated as: VH x

( ) ⊇ vmevt a ,vmevt b ,vmevt c ( ) ⇒ t a > t b > t c (
) where i denotes an ordered set.

If, given the two rules vmevt a → vmevt b and vmevt b → vmevt c , it is not the case that t c > t b > t a , then the timestamps (t a, t b, t c ) do not reflect the physical times at which the VM events must have occurred. The VM timestamps are therefore inaccurate, as they suggest an internally inconsistent chronology. From this example, the utility of the happened-before relation as a basis for proposing rules for the detection of inconsistent VM events is apparent. A hypothesized chronology of a VM computer system can be evaluated for internal inconsistencies by testing the hypothesized sequence of events against a set of happened-before rules.

Detecting Missing VM Events

There are some happened-before relations where the first VM event is a precondition for the second. In such relations, the presence of the second VM event necessarily implies the presence of the first. In the example in Section 3.1, the VM login event vmevt a must occur before the VM application execution event vmevt b ; in other words, if vmevt b occurred, then vmevt a must also have occurred. Note that this does not hold true for all happenedbefore relations. This can be seen in the same example, where although the execution event vmevt b must happen before the logout event vmevt c in order for vmevt b to happen at all, the occurrence of the logout event vmevt c does not imply that vmevt b also happened; vmevt b is not a precondition for vmevt c .

[10] extends the use of the happened-before relation of [START_REF] Boyd | Time and date issues in forensic computing a case study[END_REF][START_REF] Fidge | Logical time in distributed computing systems[END_REF] to imply causality. The happened-before relation is therefore equivalent to the "precondition" predicate. For the purposes of the log auditor, it is preferable to maintain the happened-before relation as described by [START_REF] Boyd | Time and date issues in forensic computing a case study[END_REF][START_REF] Fidge | Logical time in distributed computing systems[END_REF] and to employ the "precondition" predicate to imply a causal relationship. The happened-before relation allows for the detection of events that are listed in the timeline out of the sequence in which they must have occurred, whereas the "precondition" predicate allows for the detection of missing events.

If the VM event vmevt a that "happened" does not exist in either the set of recorded VM events, EvtR, or in the existing set of inferred VM events, EvtI, then it is a missing VM event. It is a missing VM event because it was removed from, or never recorded in the VM's hypervisor kernel logs, and it was not previously inferred on the basis of relationships and object fields. These VM events could also be called inferred VM events, but it is convenient to preserve a distinction between events detected using this approach and other VM inferred events.

Precondition VM events which are absent from EvtR and EvtI can be added to the set of missing VM events, which we call EvtM.

The VM login event vmevt a and the VM application execution event vmevt b , and the logout event vmevt c have the same definitions as in the previous example. The new rule states that if the event vmevt b occurred in the timeline of the VM User object x, then the event vmevt a must also have occurred.

Missing VM events are suspicious and hence important. They are important because it is possible to deliberately delete them from the hypervisor kernel system logs. Detecting that an event is missing allows for the construction of a more complete timeline, hence helping the VM investigator gain a more complete understanding of the VM computer system. By automatically indicating that at a particular point in the timeline an event was either not recorded or its record was deleted, the forensic software could provide a lead for the subsequent manual investigation. This, in turn, may determine why the record is missing. However, it should be noted that there are many instances where an event may be missing as a result of non-suspicious VM host computer activity.

The log auditor infers VM events to describe an action by or on an object with associated VM temporal data. These inferred VM events are combined with VM events recorded in the hypervisor kernel system logs in order to provide as complete a timeline as possible. In the experiments on computers running VMware sessions on Microsoft Windows, our software prototype inferred many VM events that occurred prior to the enabling of many logging options. There were very few recorded VM events from that early time period in the VM's computer history, and thus these inferred VM events were out-of-context. Such inferred VM events may appear to have occurred outside of the VM user sessions, or in an otherwise inconsistent fashion, however, the absence of complete information must obviously be considered in the VM investigator's assessment as to whether or not the event is suspicious. This scenario is an example of how the normal configuration of the VM computer system may make an event seem inconsistent.

VM Log Auditor Software

A summary of the VM Log Auditor architectural components are provided in Fig. 1. As a VM log inconsistency checking profile tool it maps all hypervisor events, as they are extracted from the kernel logs. It uses a set of shell script parsers to provide an associative and transformational mapping [START_REF] Thorpe | Associative Mapping Techniques for the synchronized virtual machine environment[END_REF][START_REF] Thorpe | Enforcing Data Quality Rules for the synchronized virtual machine environment[END_REF] of these logs into a normalized database with a set of discovered and inferred VM event tables. The prototype software examines the suspect target VM host file system (which is mounted read-only) and enumerates the set of VM objects of applications, files, and users of the target VMware essx3i computer system. We achieve this by performing a Storage Area Network (SAN) disk image of the suspected VM host to our evidence server in our test bed. The parsed hypervisor log events are described as the set of recorded VM events (EvtR) in our Oracle database. Finally, a set of events are inferred from the temporal data associated with each log file which may be as a result of modification, access or creation (MAC) events which have occurred. These events are the inferred VM events (EvtI), and are saved in a separate table in the database called Inferred VM Events. It is useful to note that the inferred VM events EvtI is particularly vulnerable to inconsistency or incompleteness of data obtained from the VM host file system. The two sets EvtR and EvtI do not exhaustively describe the complete history of the VM hosted computer system. Hence where an event is not logged or it cannot be inferred we described this as an unknown or missing event. It stands to reason that the more missing or unknown events the less complete the timeline of the suspect VM host computer system being investigated. Due space limitation we omit the formal completeness proof. After conducting this automated process, the software prototype provides a basic interface for the purpose of detecting temporal inconsistency in a given timeline.

The detection techniques described in this paper match the VM events in a timeline against the events in each rule being tested. Programmatically, every rule is implemented by a C# object, and every event is implemented by a C# object. Rule objects have two event objects as fields, one called vmevt a and another called vmevt b . The objects vmevt a and vmevt b are archetype VM events, against which known VM events are compared. A known VM event is compared against the archetypes on the basis of the fields of each. The fields of the archetype events can have a specific value, or be null. If the archetype has a specific value for a particular field, then any known VM event that matches the archetype must have the same value. If the archetype has a null value for a particular field, it can match any value for the known VM event's corresponding field.

The rule object can also be set to match subject and target fields, that is to say, to require that both matching VM events have the same subject or target field. The rule can also specify that the subject field of one event is the target of the other event, or vice versa. This allows for the definition of generic rules. In the object that represented this rule, vmevt a would represent the "logon" VM event, and vmevt b would represent the "modified" VM event. A Boolean field of the rule object would be set to true to indicate that the subject of each VM event had to be the same object. Given this, the values of the fields of the objects vmevt a and vmevt b would be as follows:

vmevt a = {null, null, s, logon, success} vmevt b = {null, null, null, modified, success}:

The prototype log auditor software does not yet implement the concept of a user VM session. A logon or logoff VM event is treated the same as any other event. This means that the user needs to specify which events are to be treated as the beginning and end of the user session timeline. In order to check timelines of a computer system's complete history, the prototype software would need to have a concept of user session built into it. This is an item of future work.

Rule Base for Experiments

The VM log auditor software prototype incorporates a small set of rules to check for VM temporal inconsistency. It provides a backend functionality that allows the user to specify a timeline to be checked for inconsistency. It then checks that timeline against the rule base. The rules built into the prototype software for the purposes of these experiments use the following algorithm. vmevtA = (null, null, s, "logon", "success") vmevtB = (null, null, null, "modified", "success") rule = vmevtA happened-before vmevtB where field 2 of vmevtA == x and where field 2 of vmevtB == x for each vmevt in VH(x) if vmevt = ( *, x, s, "logon", "success" ) a = index of vmevt if vmevt = ( *, x, *, "modified", "success" ) b = index of vmevt next vmevt if a > b then rule has been broken The data structures in our implementation that represented each of the archetype VM events in the rules base, had null values in place of the fields x, y.

Experimental Setup

In order to obtain data for these experiments, we employed a suspect test VMWare essx3i private network hosted computer running on Windows 7 within the University's local area network. This deployment represents our private cloud test environment for the course of the timeline experiments carried out. All system logging options were turned on in order to give us as complete a set of hypervisor event logs which are all stored in a comma delimited format (.csv) on the host oracle databases. We logged onto the VM test host computer twice for the purpose of generating two different VM user sessions: the first, an "innocent" user session, and the second, a user session in which a document was created with misleading authorship information. The details of these two sessions are described below.

We also tinkered with the detection outcomes of meddling with the hypervisor logs. For this purpose, a copy of the case file and database about the suspicious test VM host computer system inspected by the log auditor tool was provided, and then manually modified the database table containing the discovered VM events. As these discovered VM events are derived from the VMWare essx3i kernel system event logs, the removal or modification of recorded VM events in the set EvtR effectively simulates the removal or modification of VM event records in the same. The investigator removed the log-on/logoff VM events from the first user session, and modified the timestamps of these events on the second user session so that they would be presented out of their real sequence if ordered by timestamp.

Evaluation of VM Detection Techniques

This section describes each of the VM timelines examined in each these experiments and provides the results of the log auditor's analysis of inconsistency. There are four VM log timelines (two unmodified, and two modified) that correspond directly to user sessions. Each of the timelines is a combination of the VM inferred events and the recorded VM events in the history of the VM hosted computer system between two boundary events, ordered by timestamp. Due to space limitations the detailed timeline trace tables that capture the recorded and inferred events have been omitted.

Timeline A -Normal VM User Session

Timeline A was a normal user VM session during which a text document was created. The user "thorpe" logged into the VM host computer system at 9:48 pm on 12 October 2011, and created the file "vmsyslog.doc" at 9:51pm. The VM user then browsed the Internet for a few minutes and logged off at 10:00 pm. Nothing suspicious happened in the user VM session. The timeline consisted of all of the events that took place during the user VM session, both recorded and inferred. Our software inserted these VM events into its Oracle 11g VM event database during its automated examination of the target system.

Most events in timeline A were discovered events (i.e. discovered in the VMWare essx3i hypervisor kernel event logs running under Windows 7), however, the events with "CREATED", "MODIFIED" or "OPENED" as their actions were inferred events (i.e. inferred on the basis of an object, its relationships, or other information about the object).

Timeline B -Deliberate Misattribution of Authorship

Timeline B represents a user VM session during which the user created a text document with misleading authorship information, in an effort to shift responsibility for that document to an innocent third party. The user "VMuser" logged into the computer system at 9:51pm on 13 October 2011, and at 9:55pm a Word document was created with "anoynmous " as the listed author. The user "VMuser " then logged off.

Timeline B was analyzed for inconsistency with our prototype software. The events are all related to the authorship of the word document entitled "WORDOC letter from anonymous". The anonymous user was not logged in at the time the text document was created, and yet the author field listed "anonymous" as the document's author.

There are two sets of "CREATED" events for both the suspect Word document and its template. Hence "anonymous" could not have been the author of the text document. This is so because there are two sources of information that lead the log auditor inferring such an event. The earlier timestamp is obtained from the text document's metadata, and represents the time at which the document was first created. The later timestamp is obtained from the target VM host computer's file system, and is the time at which the document was first saved as a file on the host VM physical disk. Both sets of "CREATED" VM events derive their subject field from the same source, the Word document's author field .

Timeline C -VM user Session with Logon/Logoff Events Deleted

Timeline C was derived from timeline A. The recorded and inferred VM events in the prototype's events database were copied and manually modified. The resulting timeline, timeline C, was identical to timeline A without the logon/ logoff VM events. The removal of these two discovered VM events left user activity outside of a logon/logoff-bound VM user session. This demonstrates that removing VM user session information from the hypervisor event log will draw attention to the inferred VM events that took place during the session.

Timeline D -With VM user Modified Timestamps

Timeline D was derived from timeline A, with the timestamp of the user's logoff VM event deliberately modified so as to appear to have taken place prior to the creation of the text document.

The event was listed as breaking three rules, all of which assert that if a file is modified, accessed or created, it must be modified, accessed or created prior to the user logging out of the VM host computer system. The results of the analysis of timeline D were just as expected.

The detection of this VM event demonstrates the suitability of this approach to detecting events whose timestamps are modified.

Constructing Consistent Timelines

The temporal inconsistencies can be handled by the creation of a consistent VM timeline. A consistent VM timeline, in the context of VM computer profiling, is defined as a sequence of VM events ordered by physical time at which they occurred with no obviously missing VM events. The physical time at which the event occurred may or may not correspond to the VM hosted computer generated timestamp of a VM event, which may be missing from the sets EVTR and EVTI, but which are detected using the techniques that establish VM relationships via hypervisor log object profiles. EVTM is the set of all of the missing VM events detected on the basis of a precondition rule. The sequence EVTC is a sequence over EVT ordered into a consistent VM timeline. This section describes a technique for constructing such a timeline.

There are some VM events, especially members of EVTM, for which there is no timestamp. There are other VM events for which there is a timestamp, but whose timestamp is provably incorrect (as determined by detecting the out of sequence experiments). Gladyshev and Patel describe the process of determining the time at which a given event takes place by bounding the event's time [START_REF] Buchholz | A brief study of time[END_REF], and we adopt this approach for our VM log auditor tool. The upper and lower bounds for the time of an event can be determined if the VM event must have occurred between two other VM events. The range between these bounds, i.e. the time interval ∆t, is the range of possible times at which the VM event could have occurred. The range can be further narrowed if it is known that there is a minimal delay d , which applies to a particular happened-before relation [START_REF] Buchholz | A brief study of time[END_REF][START_REF] Fidge | Logical time in distributed computing systems[END_REF]. If it is known that there is at least a ten seconds greater than the time of the first event. The range of possible times at which a VM event vmevt b might have occurred can be calculated.

This approach can only provide a range of times in lieu of a missing or inaccurate timestamp, but such a range is the best possible indication of when the event occurred. As it is impossible to obtain perfect timestamps for every VM event in the history of the VM computer system, the sequence EVTC cannot be ordered on the basis of the available timestamps. The available timestamps will not be precise enough for ordering the events in and themselves, although they might be useful in determining some other basis for ordering events.

Instead of timestamps, the use of a Lamport logical clock [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] is proposed to provide the basis of ordering the consistent timeline EVTC . The timestamp (or time interval in the case of VM events with indeterminate time) of a VM event will be used as a variable in the clock, but it will be the clock and not the timestamp which will be used as the basis for ordering VM hosted events.

The VM hosted computer BIOS clock C is defined to be a function which assigns a number to every VM event in the consistent timeline EVTC. The number produced by C has no bearing on physical time, but each VM event has a timestamp t for a time interval ∆ t which can be used to determine the physical time of the VM event. The number produced by C must be lower for VM events which occurred earlier in the VM history of the computer system than the number produced for VM events which occurred later. This will permit events to be sorted by the number produced by the clock C on the ascending order basis.

Given a complete set of rules to detect inconsistent and missing VM events, the number of unknown VM events in the VM computer system's history can be minimized. The proportion of the set of all of the VM events that occurred in the VM history of the VM hosted computer system EVT that is known can be maximized. A VM event is a known event if it is an element of the sets EVTR, EVTI, or EVTM. Each of the known events will have an associated timestamp, or, in the case of VM events with no timestamps or with provably incorrect timestamps, and the narrowest possible time interval during which the event could have occurred. The clock function C will combine the timestamp or time interval for each known event with the rules relating that event to the other knowable VM events, and produce a number (i.e. Lamport timestamp) according to which the VM event may be sorted into the consistent timeline EVTC. In the case of potentially concurrent events (which have no happened-before relations to other VM events) whose timestamps or time intervals are inconclusive relative to other VM events, the number produced by C will be identical. In such cases, some arbitrary mechanism can be used to sort VM events into the consistent timeline EVTC. Once completed, the consistent timeline EVTC will represent the best sequential ordering of known events that make up the associated VM history profile.

This permits an investigator to view both a consistent timeline, and the original inconsistent timeline along with the reasoning as to why the original hypervisor temporal log data was inconsistent. Then the investigator could then make an informed judgment about the cause of the inconsistencies in the VM computer system timeline.

Discussion of Results

The results of the experiments demonstrate that automatically detecting temporal inconsistency in VM hosted computer activity timelines constructed from realistic data is possible using our tool. These experiments applied a simple rule set to a VM hosted computer system's activity timeline, and the results demonstrate that inconsistency can be detected in several basic scenarios. The happened-before relation and the precondition predicate can be used together to construct effective rules to draw an investigator's attention to suspicious VM events. Timeline B demonstrated that such rules can be applied to detect an event (in this case, the creation of a document) initiated by a different user than first suggested by the VM file system. Timeline C showed that the deletion of a hypervisor kernel system log set of entries pertaining to important VM events can be detected. If the deleted events are preconditions for other events, which are recorded or inferred, then they can be detected. Timeline D demonstrated that, by applying a rational set of rules in an automated analysis of a timeline, VM events can be detected that should have occurred in another sequence than their timestamps suggest.

The experiment's use of data from a VM hosted computer system demonstrated that this approach to detecting temporal inconsistency on VM log data is robust enough to be tested in real cases. The ideal next step will be to perform experiments with the log auditor using large scale live incident case data, which will test the robustness and suitability of the approach with respect to real investigations.

The noise in real VM event data is a lesser problem to the VM log auditing tool than it is to a human investigator. By distilling VM event records down to the most important fields that are common to most events, our approach is likely to reduce the complexity and heterogeneity of the various types of VM events.

Future Work

We plan to improve the log auditor so that the software can automatically detect user sessions given our ongoing work [START_REF] Thorpe | Towards a Formal Parameterized Context for a Cloud Computing Forensic Database[END_REF]. At the moment, the prototype software requires the user to specify the bounds (i.e. start and finish) of a user VM session before it is able to check the timeline of that VM session for internal consistency.

We would like to extend the VM log auditor process and software to construct consistency-check timelines of VM hosted computers running non-Windows operating systems.

The basic model presented in this paper doesn't detect hidden nested states that may exist on the VM host as extracted from the hypervisor logs particularly as a remote or distributed logging service. We plan to extend the existing model to now explore and formalize this concurrency problem.

Related Work

Although there has not been any formal accepted definition for cloud forensics, its fundamentals are still entrenched in a view that the data provided as case evidence has to be court admissible. The provision of a time-lining technique together with the practical approaches for gathering and inferring VM events comprise a technique for tracing the history of the VM hosted computer system as possible source of such potential forensic evidence is motivated by prior work [START_REF] Thorpe | A Virtual Machine History Model Framework for a Data Cloud Investigation[END_REF][START_REF] Srinivas | Trail of Bytes: Efficient support for Forensic Analysis[END_REF][START_REF] Gidwani | A Comprehensive Survey of Event Analytics[END_REF][START_REF] Pauw | Visual and algorithmic tooling for system trace analysis: A case study[END_REF]. In this paper, we attempt to improve on the state of the art by providing a forensic platform that transparently and distinctively monitors and records data access events using the hypervisor kernel event logs. This work adopts a static state snapshot log approach to support post incident off line forensic investigations. Our work complements the live trace analysis and VM introspection methods [START_REF] Srinivas | Trail of Bytes: Efficient support for Forensic Analysis[END_REF][START_REF] Gidwani | A Comprehensive Survey of Event Analytics[END_REF][START_REF] Pauw | Visual and algorithmic tooling for system trace analysis: A case study[END_REF] and the static snapshot finite state hypothesis computational models [START_REF] Fidge | Logical time in distributed computing systems[END_REF][START_REF] Gladyshev | Formalizing event time bounding in digital investigations[END_REF][START_REF] Schatz | A correlation method for establishing provenance of timestamps in digital evidence[END_REF].

Conclusion

This work has produced a tool, implementing techniques for detecting contradictory and missing VM events in the history of the computer system. The experiments with this software demonstrate that the techniques that have been proposed can be used successfully to detect temporal inconsistencies in a VM computer activity timeline. The automatic detection of inconsistencies that might indicate deliberate tampering could assist a human investigator in a subsequent manual examination of the VM hosted system running within the data center.

Fig. 1 :

 1 Fig. 1: Architectural components of the VM log auditor prototype

Fig. 2 :

 2 Fig. 2: VM Inconsistency Algorithm