Hi everyone. Hi everyone and welcome to my talk. Good morning or good afternoon or good evening wherever you are. I want to start by thanking Alina, Mike and Philip for giving me the opportunity at speaking at this prestigious seminar. This talk I have already given parts of it in other places, for example, the BAMF meeting in September that Alina was one of the co-organizers and the conference in Debrates in last summer and at the couple of places in South Africa. But hopefully for some of you, some of these things will be new. So let's move on. So my talk is about recent progress on the school and problem. My co-authors are depicted here, Joel Waknin. He's a director of the Max Park Institute for Software Systems in Sarbrookin. And the colleague depicted on the right, James Worrell, he is a professor at Computer Science at Oxford. And there is them, they visited me in South Africa. In January of last year, here is them a picture with Poar Tambo in the airport. Okay, so let's go and let's say what is the school and problem. So the basic question is what is the simplest class of programs for which deciding termination or halting is not obvious. And the answer is simple linear loops. So here is what you do when you're a student and you maybe take the first time a course in computers in computer science and you learn some loops. So you have three initial values for XYZ and while X is not equal to zero, you have to reassign these values of the variables so XYZ goes into 2X plus Y, Y goes into Y plus three minus Z, Z goes into minus four Z plus six. So the general problem is while X start with some vector a and while the first component of the vector X is not equal to zero. So let's move X to M times X where M is sub matrix. Well, this example is not exactly like that. There is also some shift, but let's take this as the simplest example. So the first one is called the school and problem because it's, you need to decide when is X someone different than zero because if X sub one is equal to zero then you stop. The problem is called the positivity problem because while the first coordinate is at least zero then you can continue and if the first coordinate ends up being negative then you have to stop.  So the school and problem says start with the square matrix K by K M. And the question is, is there a positive integer N such that the top right entry of M to the power N is equal to zero and the top right entry is just something we chose we could ask for any particular IJ entry. The question is the same question is that that you are not asking if it is exactly zero but you're asking if for every end into the power and is greater equal to zero. And this boil this can be recast in terms of linear recurrent sequences. The sequence is a sequence for us the members are always going to be in Z or in Q so they're going to be integers or rational numbers, such that they are constant say 182 AK with the property that UN plus case a linear combination of the previous K terms with the coefficient say 182 respectively AK. The example is the Fibonacci numbers which starts with zero one and then every term is the sum of the previous two terms, the length of the minimal recurrence it's called the order of the sequence. And the school and problem now, and be reformulated in terms of zeros of the linear recurrent sequences you are given a linear recurrent sequence. The question is does there exist an n greater equal to zero, such that you sub n is equal to zero. And the positivity problem is, is it the case that for every n greater equal to zero you sub n is greatly equal to zero. And believe it or not, these things are still open in general. Here are some quotes from some famous colleagues. The question is that is it fate outrageous that this problem is still open. And Richard Lipton it calls it mathematical embarrassment the most prominent problem whose decidability status is currently unknown. Now a fact every nearly recurrent sequence can be finitely decomposed into finitely many where they are called non degenerate linearly current sequence.  Then if you think about it, this sequence is constant every two other terms. So then you can say that the minimal recurrence is UN plus two is equal to UN. That's a linearly recurrent sequence of order two. Now what does it mean not generate these linearly recurrent sequence you can associate something which is called the characteristic polynomial, which is going to appear later on slides but what it basically is. You take this relation from here, and you write down the polynomial x to the power k minus a one x to the power k minus one and so on down minus to a sub k. You compute the roots of this polynomial. And then the general theorem says that you sub n is a linear combination with some coefficients, which might be polynomials in N of those distinct roots to the power n. So in the example that I gave you with you sub n plus two is equal to you sub and the polynomial is x square minus one. It has roots plus minus one so the answer is one to the n plus minus one to the end. Now here's where degenerate the alias comes into the picture a sequence is called degenerate if there is this the ratio of these two roots which is a root of unity. If there is a ratio of these two roots which is a root of unity like in the case of one to the n plus minus one to the end then that sequence can collapse on an entire arithmetic progression of indices. All that can happen in some sense, so you take that linear recurrence sequence, you look you say aha there are some roots of unity among these ratios you get rid of them by choosing a sufficiently large number m, such that if all these roots of unity to power m become one, and now you split your sequence along residue classes module M. So you get m of them depending on whether n is zero one or two up to m minus one module of that modules and each one of these itself is a linear recurrence sequence now. And these ones are all non degenerate except that some of them might be identically zero like in the example that I gave you with UN is odd if n is equal to it's any odd UN is zero if n is odd and UN is two if n is even. This so that the theorem is that after you get rid of the degeneracy is the scholar mother leg theorem says that the set of zeros of a non degenerate linear recurrence sequence is fine. And the decidability is somehow equivalent to being able to compute the finite set of zeros of any given non degenerate linear recurrence sequence. Fortunately all known proofs of the scholar mother leg theorem make use of the non constructive techniques so there is the classical proofs, which use pediatric analysis, which somehow pick a prime P, which is a convenient prime. In one section your sequence along some number M, such that let's say all these roots are M is a common order of all these roots, modulo p so alpha the power M is congruent one module of P, which means that alpha to the M power x is congruent one module of P and this one you can express is a periodic function by writing alpha to the MX is being the exponential of the logarithm of itself. And you're applying the logarithm to some number which periodically is equal to one so you can write this number is one plus itself minus one which periodically is equal to zero you expand it. And then you do what you do in calculus. But and then you get some analytic function and then you say okay this analytic function the pedics are compact therefore it has only finite many zeros, but you cannot extract information about how big those zeros are, and they are more modern than using the subspace theorem and so on which gives you information about how many of such zeros. Can there be work of Schmitt and Schlich via so on but again, these are known effectively tells you up a balance which we believe they are very far from the truth because they are double triple exponentials in some parameters of the sequence, which is the sequence cannot have more than this many zeros. Now the school and problem and the positivity problem arise in several areas, for example in theoretical biology population dynamics software verification dynamical systems, weighted automata in games control theory, formal power series and combinatorics and so on. So for example does our example finish. Let's go back to the example that we started with. It turns out that x is never equal to zero module of three and to see why that is like this look at this module of three. So it starts with one zero zero module of three these two numbers are zero so they disappear. The beginning goes from one to two, and then the other two numbers stay zero. So after the first step you start with one zero zero get to zero zero you do it again. You get four zero zero but four is equal to one module of three so you get back to where you were. So in some sense this is a sequence which is periodic of periods three if periods to, and we can see that the only values are one and two so it will never stop it will never be zero. So this is the Fibonacci variant of course you should forget about the fact that the Fibonacci numbers are positive. We will try to use sort of periodic information about it to decide what's what. So if you started the Fibonacci variant that starts with two and one which is the so called Lucas sequence. And this one you can detect it for example module of five it has no zero, because it's a of length four, and it's a period of length four which is 2134 so it takes all the non zero classes module of five but it doesn't take the zero class. How about the shifted Fibonacci sequence I started with zero and one so I already gave it away that there's a zero there but then I may say let me delete that zero and be a bit tricky and I start with one and one. But now if I take it math to I reduce it math to I notice that every third number is even so if any zero math three, then, then f of n is even. If I took it math three, then every fourth multiple every multiple of four, it becomes zero math three module of four every multiple of six. So many families a multiple of six is zero math for what five the period is 20. This is that this one one here and it continues all over there but inside the period of length 20, you have four zeros. So inside this period in fact you have every residue class appears exactly for time. So this means that for the Fibonacci sequence a modular argument can never work in some sense if you have some zero then that zero modularly will be there. It doesn't matter if you decide to delete some terms of your sequence and started very far away once you reduce it module or something. It is always periodic. And the theorem says that it's purely periodic, especially if the modulus is co-prime to the last coefficients of the recurrence. If the period is not co-prime module of the last coefficient of the recurrence it might not be purely periodic think about x sub n plus one equal to x sub n and you start with one. You should get you get powers of two if I reduce this module over 32. Of course it's going to be periodic is going to be equal to zero after a certain number of steps but at the beginning it isn't so it has some pre period. But if the module of m is co-prime to the last coefficient this phenomenon doesn't happen and it's periodic from the very beginning. Fibonacci sequence if you shift it doesn't contain a zero but modularly you can see that it's somehow haunted by the ghost of a zero in its past. Okay, one of the things we like to do it's you like to go back with them. So what does it mean to go back well I think of this recurrence if I want to extend it to the left of zero what do I do well I know how much is you sub zero and I know how much is you are zero and one. What do I have to put to the left of zero such that the sum of that number with zero is one well I have to put the number one and what do I have to put to the left of that one. Such that the sum of that number with the number one is zero is the number minus one and you get this. A minute of reflection will convince you that the numbers is the same numbers that you get as the Fibonacci numbers except that there's a change of sign when n is even. So minus one to the n minus one f sub minus n is equal to minus one to the exponent n minus one times f sub n. Here is the classical arithmetic progression. And this one you can always extend it in the past. Now this sequence, you can go with it in the past, but when you go with it in the past then you're going to get rational numbers you're no longer going to get into chairs. There's two to be zero reversible and this one to not to not be zero reversible meaning you can always go back into the past except that you're not going to end up with integers. You're going to end up with rational numbers, but these rational numbers are not that complicated if you think about it if you have some coefficient a sub k at the very end here. There's no time when you want to extract the next term you're basically dividing into that coefficient so those rational numbers are not that complicated they are just divisible by the primes that divide the last coefficients of your recurrence. So let's formulate the bicycle and problem I take the bilinear recurrence sequence it's over Q. Does there exist an integer n such that you sub n is equal to zero. Let's go and call the character the linear recurrence sequence we will call it simple if it's characteristic roots are simple. That is that minimal polynomial that you have has only simple roots in here the minimal polynomials are x square minus x minus one it has simple roots this is x minus one square because it's an arithmetic regression. It's a linear combination of one and end so this one is not simple and that one is simple. It's a monarchy sequence it's simple. The vast majority of them are simple but of course not all of them are, if you think of it in terms of matrices, then the simple ones correspond to diagonalizable matrices. What can we say about those zeros can we actually compute them, or let's say can we decide if it has a zero what there's various ways in which you can make that decision. The simplest decision would be to have some formula saying that all the largest zero of these linear recurrence sequences smaller than some function, which depends on the length of the sequence the magnitude of the coefficients and the magnitude of the initial terms. So there's a result from 84 and also independent from 85 by me not sure it tie the money and very shagging where they prove that linearly recurrence sequences of order at most for this column problem is decidable. And what sits inside that it's basically a count on the number of roots of maximum absolute value. So if you have a route which is a maximum absolute value and it's by itself and the contribution of that route to power and it's going to beat everything. From some point on which you can write down what it is so that is easy if you have one route which is of absolute maximum absolute value. If you have two roots which are of maximum absolute value this means that they are a root that it's complex conjugate and the ratio of them is not a unity because they are not degenerate. So if you have two competing forces, the root alpha to the power n and the root alpha bar to the power and maybe with some coefficients which might even be polynomial in it. Well it turns out that this can be a little bit smaller than the absolute value of alpha to the end but thanks to the Baker method this can be much smaller you're only losing let's say a polynomial factor in N. So this contribution from these two maximum roots, it's at least the absolute value of this term maybe divided by some power of n, but you're keeping the exponential character growth character of it and because of that you can also solve it. Now you can even do it for three roots but that is characteristic to the fact that the sequence has integer terms, because if you have exactly three roots of maximum absolute value then they are a number it's conjugate and the absolute numbers. So if you write some linear expression in those ones to the power n and you factor out the absolute value of that number to the power n, then you're basically left with some trinomial in the number let's call it T, which is the trinomial it's the number T is going to be e to the i n theta where theta is let's say the argument of alpha so we have some coefficient times e to the i n theta, plus some other coefficient times the conjugate of that which is its reciprocal, plus the third coefficient and that's a quadratic polynomial into which you can factor and when you factor it becomes a product of two binary things T minus something where T is e to the i n theta. So there you can do Baker's method again so because of that they win and actually they win even if you have the same argument shows that if you have at most three roots, which somehow are dominant in some pediatric value valuation then you win, you either use, if they are dominant as complex then you use some infinite valuation and if not you use some some finite valuation and this is the critical ingredient as I explained is Baker's theory. So for linearly recurrent sequence of order at most for the bias column is decided. And we have some contribution last year with his colleagues with Richard Lipton juries new felon is a PhD student of Israel, Israel David person was opposed over that time and start broken. We prove that if the sequence is reversible of order at most seven this column problem is decided, but that's a little gallery primary problem because basically we we used this what we know that it can have let's say, if you have at most three dominant roots and you're fine. But having the notion of reversibility this means that these roots are actually units because the polynomial that you're looking at has the last coefficients plus minus one. And then you can ask how ugly can that polynomial be so that all its roots are units and at least three of them are at least four of them have the same absolute value and you prove that polynomials of degree at most seven cannot have that proper. But there is examples of polynomial as a degree eight that have that problem. This is why our argument breaks down there. And there is an older result of about 10 years ago about positivity, which is decidable for generally current sequences up to five of Israel and Ben. And then if you further impose simplicity, then it's decidable up to nine. Okay, so now since we can't do better. It's time to throw in some conjectures into the pot. So many problems in mathematics and computer science are so subject to various standard conjectures. For example, Riemann's hypothesis, or the belief that factoring is not in polynomial time that depends the security of RSA. The decidability of the first order theory of real arithmetic with the explanation is subject to channels conjecture. So since I mentioned channel conjecture. Let's recall what the channel conjecture is. So channel conjecture the following take n complex numbers which are linearly independent of the queue. And look at the field obtained by adjoining these two n numbers to queue, which are the numbers you start with, and their exponentials. So the theorem that conjecture is that the degree of transcendence of this field is at least and equivalently if you have n complex numbers which are linearly independent over q. And then within this set of two n numbers one can find at least n of them, which are algebraically independent over q. And you can see why the condition of linearly independent over q is because if, for example, one number is the sum of the other two that the exponential of that number is the product of the expression of the other two. So you need some linearly independent condition. Some examples we know that is transcendental we know that pie is transcendental what about E plus pi and E pi. Of course they can't be both algebraic because if they are both algebraic then E plus pi and E pi algebraic so this polynomial, which has E and pi as roots is a polynomial with algebraic coefficients. So this makes one of them transcendental, but which one, probably both of them are transcendental, but we don't know that what about other more complicated examples like this one. So let's apply the channel conjecture with the two numbers one and I pi. The channel conjecture says that within this set one I pi e to the one e to the I pi, there should be two numbers which are algebraically independent, but e to the I pi is negative one. So the only two numbers that can be algebraically independent are those two I pi and E and E is algebraic and I is algebraic so pi and E should be algebraically independent. For any non zero polynomial with rational algebraic coefficients we should have that P of the pair E pi cannot be zero. In particular those examples must all be irrational assuming this conjecture. So in particular channels conjecture implies that there are no algebraic relationships, you can write something like that but that's not an algebraic relation. Okay, what does this have to do with our linear recurrence sequence. So let's start with the linear recurrence sequence let's reverse it. Now we are assuming in general we will assume shortly that it's simple but for now we no longer assume that a sub case plus minus one so that it is reversible but it can be any number at once. But now I take a modulus m which is co prime to a sub k. Since it's co prime to a sub k and thinks that this is a sequence module and it behaves like the interest. So for example this sequence if I reduce it mod three becomes that sequence and if I reduce it mod five it becomes that sequence so the prime three doesn't care that I'm dividing by things. Because for the prime three a sub k, I can divide by it because it's inverse it's also well defined module. There is a fairly wide ranging conjectures formulated in 1937, which is known as the exponential local global principle. And like channels conjecture is wildly believed by number theories but only proven in special case. So what this column conjecture is considered this recurrence relation, and suppose that the sequence is simple there's some reason for that and I'll give you a counter example as to why this conjecture is false for non simple sequences. The conjecture says that the sequence has no zeros. If and only for some integer m which is co prime to K, we have that you sub n is not zero model. So in some sense whether this conjecture says the conjecture says that if the sequence has no zero, then there must be a modules that notices that that witnesses the fact that there is no zero. So, why is it false for non simple sequences well I can give you the one of the easiest example is a sequence of the form two to the power n times to n plus one. This sequence doesn't have any zero even if you go to negative numbers it's still not going to have any zero where it has a rational zero but let's not count that one. Which is at minus one half so I have two to the n plus one, two to the power n multiplied with two and plus one does this have a zero module every m which is my love every m. And I say of course it does because when you look at two to the n times two and plus one. You can put the power of two you're already winning it for free for large and so you can look only at the odd part of M, but then you solve to n plus one is equal to zero module of the odd part of M and you get a solution. So you get infinity main solution so that will have zeros much no any m. Now we proved that the school in problem for linear recurrence sequences of order five is decidable assuming just the school and trajectory. So that is one small step as we said before we could do it up to four now we can do it with five. But which whether they're simple or not. There is a very important theorem in the section. There is an algorithm which takes as inputs, a simple non degenerate linear recurrence sequence and produce it is finite set of zeros. And the termination is guaranteed assuming the school and conjecture and the periodic channel conjecture. And the way this argument works is the following. So there's two problems there problem number one decide if the sequence has a sick as a zero. And number two find all the zeros of that sequence. Well if you only assume the school and conjecture then you can already solve problem number one. And here is how you do you start to algorithms. Two programs one of them is looking for zeros and one of them is looking for witnesses that there are no zeros. So one of them goes through all the modules and go crime to a K and calculates the values of you sub and module and which you can do in finitely many steps because the sequence is periodic. And if the school and conjecture is true then one of the two algorithms will stop either there is a zero and the first algorithm will find it either there's no zero and the second will find a witness that there's no zero. So so far, we can construct just out of the school and conjecture we can find whether there is a zero or not using these two things. Now, what about finding all the zeros. So as I said, well, the important thing to mention here is that we actually implemented this algorithm and this algorithm is only needed to prove termination not correctness. So the algorithm, if it works is going to produce a correctness certificate which is independent of all the conjectures the only thing that is needed for the only way that the only part of the proof that needs those conjectures is to show that this algorithm actually terminates. And it's implemented in this online tool which is called school so if you want to get school and you can you can go here. Or it's accessible from the web page of my colleague Joel working in you go to his web page there is some software that he has he and his team have developed and this is one of them. So what does the school and problem do you're going to be faced with this. You're going to have to promise that the sequence that you're given is simple that you're not trying to trick it by giving it polynomials with multiple roots and so on. You give those values and those the initial values and the coefficients, and it will produce some lists, and it will say for example here are the zeros. This particular example that at zero one and four, and then there's a list, and the list says, these are the only zeros as it can be proved by this sequence of congruences. So, all the other ends which are not one of those they are going to be trapped in some congruence. There is some congruence class module some modules, such which is congruent to that number in which is not a zero for which when is not zero module that module. The key technical tool. The key technical tool is the following started the non degenerate linearly current sequence. Do the algorithm that I said that you do you have these two algorithms one of them which looks for zero one of which looks for witnesses. If you find a witness that it's not zero then you're done. And it's over there's no zeros. So let's suppose the first algorithm finds a zero then what do you do next. Well what you do next you can shift that zero into the origin. Now you have to go further. So how can you go further here is the important lemma assuming the periodic channel conjecture one can compute an integer m, such that if you look at this sequence, only over the multiples of that integer m. Then that sequence has no other zeros. This is the key technical lemma, meaning it has a zero where little n is equal to zero but for little n greater equal to one it has no zero. If you have that you have that then you're basically done. Because why is it then you're done well you compute this number capital M this is what actually the program does it compute this number capital M. Now once you says find this number. It splits and into residue classes module capital M, and says let's go through the residue class, let's say our module capital M well if R is equal to zero, this is exactly the sequence. And the lemma says there is no further zeros there don't bother going that way you should just look at the other M minus one sequences. So now you re-intitiate your problem with every one of these M minus one sequences and you start either looking for zero witnesses and so on and the fact that there's only 590 many zeros will guarantee that this procedure terminates. So where do we assume the periodic channel conjecture we have to assume something about so. As I said you take, as I mentioned in the older proofs of the Schole-Maler-Lech you take some suitable prime P, you associate some analytic function, and you have to look at the zeros of this analytic function. And so you have to look at let's say some of the periodic zero you have a this is you're in zero you have a periodic zero there. And then you have to look at the expansion around the zero, but when you look at the exponential of the logarithm of something times x and you expand that in series. Then of course the first term is zero but what's the next term the next term is basically the first derivative. And the first derivative of the exponential of the log is the log so that the first derivative is a linear combination those books and the second derivative is a quadratic polynomial which is homogeneous. Which is homogeneous in those logs. And the third derivative is a cubic polynomial which is homogeneous in those logs and so on. So, maybe if you're in the first case you can get away by periodic Baker's method and so on. Oh, maybe if it's not zero then I can even bounded and but as you go to quadratic relations among the logs cubic relations among the logs then you are stuck. And so on conditional results and that's where we are assuming the periodic channel conjecture, meaning that if there is no obvious relation between those logs. Then that coefficient is non zero and then you can apply stress months there were more something like that. The resulting sequence is guaranteed not to contain any zeros and then independent correctness certificate can be produced. And this periodic channel conjecture is only needed to ensure termination namely being able to calculate this number capital F.  That's something very complicated at the end. All right. Okay, so let me go over this one. Okay, so now I have another maybe. What is it 20 minutes 15 minutes. Let me talk about the different topics so so far. So my presentation is called progress on the school and problems we made some progress on the school and problem assuming two conjectures. And we basically solved it for simple linear recurrence sequences assuming these two conjectures. Now we said let's initiate a different program. So the program that gave us some conditional results which was based on the Baker method and so on was based on the enumeration of those roots of dominant absolute value so if you don't have too many of those roots then somehow you can have a lot of cancellation. Of course thanks to the subspace there and you know that you don't have enough, you don't have too much calculation for large and so this independently of how many dominant roots you have. You still don't have a lot of cancellation for large and but you don't know what large and means. So this. Tell what we initiated we initiated a different thing instead of saying that the sequence is bad and the integer is good we said that this all the sequences are good and the integer some of them are bad and some of them are good. So the good integers are the integers for which you can test any linearly recurrent sequence whether it has a zero in that integer. And the bad integers are the integers for which we don't know how to do that. So let's say that s is a universal square M set if there is an effective procedure such that given a linear recurrence sequence you outputs whether or not there is an integer any of this set such that you sub n is equal to zero. And we stole this definition from the notion of a universal Hilbert said. What is the universal Hilbert sets so Hilbert's theorem says the following let's start with the polynomial which is a polynomial with rational co efficiency, which is irreducible as a polynomial in two variable for which is not linear or constant in X so excess degree at least two. And then you can ask okay fine let's start evaluating this polynomial in some integers make y equal to some integer then I get some polynomial of one variable. One variable a degree at least two sometimes is irreducible sometimes is not and what can you say about the irreducibility of it. So Hilbert's irreducibility theorem asserts that the set of integers for which P of capital X and n is reducible is of density zero. So most integers that you're going to stick into here, the polynomial as one variable of X is going to keep the property of being irreducible. So that's the difference of measure or density so the number of those ends of absolute value at most T. If I divide that number by T and I make T go to infinity, then this number this limit is zero. And SD Cohen proved that, in fact, this set is. T to the one half multiplied by log T so it's really thin. This, this little off team applied by this limit it's not like the primes but it's more like the square roots. But they are polynomials for which you do get the square roots. For example, x square minus y, if you evaluate why to be a perfect square then this polynomial of course factors and up to T they are about square root of T perfect if why isn't an integer which is not a perfect square then it does affect. So motivated by such a result the universal Hilbert set is an infinite set of engines with the property that it intersects this bad set transversely in only finitely many points for every irreducible polynomials p of x y with values with rational coefficients to prove gave with explicit example, it showed that the set of integers of the form m cube plus this little thing the integer part of double log of the absolute value of m this is a universal Hilbert set. So whenever you take any polynomial of the great list to in X, which is irreducible and you make why to be equal to a member of this guy. Then you get the diophantine equation. And this diophantine equation has only finite many solutions as a diophantine equation in the variable X and integer m. And philosophy and Wilcox constructed a dense universal Hilbert set. So the first one that we constructed was in 2021. So here is this range construction take the following function which is defined on the set of natural numbers except for zero, which takes n and it sends it to something a little bit smaller than log n which should be an integer. So the little bit smaller we chose it to be square root of log n but you can choose log n to two thirds or the one minus f silent and define the following sequence. The zero term is one and the nth term is the factorial event, plus the value in the seat of the sequence in the index f of n, where f of n is given by this. So this definition is somehow recursively calling itself, but since f of n is strictly smaller than and by the time you get to this step, everything else before that has already been defined so. So you can I even list this but look how slowly this grow so basically what S of n is this some huge factorial plus some tiny factorial about like the factorial of the square root of log of n integer part plus something which is the factorial of the square root of log of the previous one so it's basically like a double log and so on so the nth term is basically a sum of a few factorials but each one of them goes down very quickly to zero. And I claim that this one is the universal column set well you see when I say that something is universal column said it's not enough for me to show you the set. I also have to take to explain to you what am I doing how can I make sure how can I compute the, the set of zeros of any linearly current sequence in this sequence because otherwise why would you believe me that this is a universal column set. So here is the important lemma suppose that UN is given by this minimal recurrence, I take delta to be the discriminant of this characteristic polynomial. Actually this delta might be zero it's better to take delta to be the maybe the discriminant of the decomposition field of this polynomial or something like that. So the proposition is the following take this linearly recurrent sequence, take a prime, which is small enough, but it can be any prime other than finitely many bad prime so the bad primes are the primes which divide this coefficient, meaning somewhere in some extension there might be some prime idea that divides the roots, and then divide the discriminant of the field or at the polynomial and so on.  And the proof of this it's very easy it's basically Fermat's theorem in algebraic number field. So what you do you look at let's say alpha is a characteristic root of that sequence. In that sequence it's a linear combination of alpha to this inputs and so I look at alpha to the power n plus m factorial. So this is very small alpha let's say it's invertible much low P this means that it's going to have some order. And the order of it divides something of the form P to the F minus one where F is it say the inertia of some prime ideal sitting over P. But the point is that P to the F minus one is at most P to the D minus one which is a part of m factorial. And then the factorial disappears much low P and it becomes so alpha to the n plus m factorial becomes just alpha to the end. So in particular this congruences through so this is you just write down the characteristic equation and you prove it. So in particular here is why this universal school M said suppose that USF of S of n equal to zero and write down the formula of S of n it's n factorial plus S which is much smaller. So you multiply this previous lemma in here. This previous lemma in here it tells you basically that you can get rid of this factorial and that USS of F of n is going to be zero much low P for a bunch of primes what does it mean a bunch of primes, all but finitely many of them, and all of them to the one over D and you multiply these primes together up to n to the one over D and by the prime number theorem, you get the exponential of log of n, the exponential of n to the one over D. And the exponential of n to the one over D, it's the double exponential of log of n divided by D. But how big is this guy, this guy is basically, let's say the dominant root in S of F of n and S of F of n is like the factorial of F of n. And the factorial of F of n, so it's the exponential, we have one exponential because of the root you get another exponential because of the factorial, but it's basically the double exponential of F of n. And this is why we chose F of n to be here, because this function is much smaller than the exponential of double logarithm of n to the power D. And now you use this argument that says that if an integer divides another integer which is of a smaller size, then the other integer has to be the integer zero. So this means that this being zero forces this being zero. And now it's perfect. Now you have a little machine. If it's zero, then the next one is zero and the next one is there and you keep on going down. But you see now you get too many zeros of this linearly recurrent sequence we have very concrete bounds on how many of them they can be. For example, there's a result of Schlegel by that of Schmitt that says that the number of zeros of a linearly recurrent sequence of order case that most triple expansion in case of most X of X of K of something X of X of X of three K low K, and he doesn't even assume that this sequence has integer coefficients it could be any complex numbers for initial values and recurrence and so on. So, actually this was a cute six page paper it even got some distinguished paper where that the conference in logic in computer science. So this is our set well the set is not very thick. Since the S of n is up to X and it's a bit like factorial that is very, very low. So can we do better. And then we say that yes we can do better. And this is one of my last slides. This is a very complicated slide but I will try to explain the content of it. So basically looks up K of X is going to be the iterated logarithm of X, so this is three fold iterated logarithm of X. Now for X efficiently large. Choose two sets of numbers, a of X and B of X, a of X is up to about square root of log X. And just to make things easy consider primes in here, and you chop off the beginning of a few of them because of some technical reasons. So basically you can you consider a dyadic interval, which starts around something that's little o of log of X. That's like, let's say log of X over the square root of triple log X now with this two statistics take a number between X and two X, and try to represent it in the following way. And then look for representations of the form Q capital P plus a, where Q is a prime in here is an integer in there, and the result capital P is whatever comes out of this equation. Now you might say how do you even do that. Well, it's easy. Let me explain to you how to do that you fix the number and, and you fix a prime Q in here. And then Q, what's left are a and P. Now for this equation to make sense in integers, a has to be known modulo q because q is already fixed and then is fixed so a has to be known modulo q. So you go into this interval and you say, Okay, let me pick up numbers in here, I can pick up any number I want. It just has to be correct module A, but see a goes up the square root of log X. So this interval has size around log X, you lose a little bit so this interval has size roughly log X divided by a time this fudgy. So you certainly have many candidates, all of those all those candidates when you compute the expression and minus a over Q you're going to get integers. And every now and then these integers are primes. And enough of them are primes that said this quadruple log of X or something like that and you have some other technical conditions. Then you say the integer n is good, and you put it in your set, the set of good integers. I claim that the set of good integers is a universal square m set. And why is that. Well, let's go back to that expression with, let's say linear combination of powers of alpha to the n where alpha is some number. So we try to use the same argument as we used before the visibility with some prime p. So the divisibility some prime p is going to be this prime. So I look at alpha to the power n, and I write n as being little q times p plus a well alpha to the power p let's assume that we are in the fortunate case like Fermat's little theory. So alpha to the power p becomes one much low piece so it goes away. So alpha to the power and becomes alpha to the q plus a. So asking a view sub n is equal to zero basically is asking for you in the index q plus a to be equal to zero. So look at q plus a q plus a is little all of log x, and the prime p is around x, so this is the exponential of the log of x.  It's equal to zero many times because this has many representation, but we have a formula we say that the number of zeros cannot be too big. This means that the number of zero which is at least quadruple log x is bounded by let's say the triple exponential in k. So we get that x or n is bounded by a seven fold exponential in k. And this is true inside the set, of course there is more things to do because maybe alpha to the p is not necessarily equal to alpha might be some conjugate of alpha. So, so there's more things going into here. And why is this a positive density. This is a positive density because you can use Koshy Schwartz. You can use Koshy Schwartz and you compute the sum of the number of representations of any in this way, and you get some obvious up about.   And this positive proportion is the proportion one, and because basically the bag of numbers that we are associated to it grows a little bit larger than the logarithm of x to every end, which means that we should get enough primes to do that. Okay, if you go through some, for example we contacted young Hendrik ever say and he pointed out some interesting references, and using that we said well in our set which is a positive lower density, all the solutions of all the zeros of this sequence satisfy this inequality, except three is the triple fold explanation in a except five is the quintuple explanation in those parameters where this is if you want the complexity of the sequence how big it is the start how long it is, and how large the coefficients and initial values are. And, and this is what I wanted to show you so I wanted to show something about the school and problem, the positivity problem is even less is known. And that's it I will stop here.


How much can I earn teaching English in Poland? It is said that Poland has more available positions for ESL teachers than any other country in Europe. While most teachers find it difficult to save a great deal, the average salary of 600 to 1000 US dollars per month should be enough to enjoy a comfortable lifestyle. Poland has a huge demand for ESL teachers in many parts of the country, making it an ideal destination for first-time teachers looking to gain valuable classroom experience. As Poland is a member of the EU, it is very easy for other EU nationals to simply turn up in their city of choice and quickly find work as there are no visa restrictions. While it is not impossible for non-EU citizens to acquire a work permit from within the country, it is often more convenient to secure a position via an online job site and then apply for the appropriate visa from a Polish consulate within your own country. Jobs can be found in almost every part of the country. However, major cities such as Warsaw, Krakow, Lodz and Roklaw offer the most numerous options. Salary Although teaching jobs are plentiful across Poland, average salaries are not as high as you will find in many Western European countries. However, the average monthly income of US$600 to US$1,000 is considerably more than the average local wage and is generally enough to live comfortably on. Teachers who find they need extra cash to fuel a busy social life, to pay off student loans or for further travel, commonly take on private students in their spare time. Hourly rates for private tutoring range from US$10 to US$20 depending on experience and location. Employers The most common employers of foreign ESL teachers in Poland are private language schools that can be found in all major towns and cities. The vast majority of employers will expect their teachers to hold a degree in any subject and the addition of a TEFL certification will allow you to apply for jobs with higher salaries and better working conditions. Some employers will help you out when it comes to applying for a work permit and many will also help with finding accommodation. The number of hours of actual teaching varies from school to school but on average teachers spend between 20 and 30 hours per week in the classroom. Cost of living The cost of living in Poland varies depending on your location and lifestyle. However, most teachers should find they can live comfortably on their income. In comparison to much of Europe, basic costs such as groceries, public transport and utility bills are relatively cheap. One area where costs have risen in recent years is accommodation. While it is possible to rent a one bedroom apartment away from the city center for around US$300 per month, many teachers choose to reduce their costs by renting a room in an apartment shared with friends or colleagues. Apartment sharing is particularly common in Warsaw where rents tend to be considerably higher than other areas.


Okay. Hello, everyone. My name is Paramot Kid and I welcome you to Reversing with Dynamic Data Resolver. If you are not already in the Discord chat, please go to BlueTimulus.org. Click on the Discord channel link and I would like you to give a warm welcome to Mr. Holger and let's start with the talk. Hi and welcome to my presentation, Reversing with Dynamic Data Resolver best practices. My name is Holger Unterwing. I'm a security researcher at Cisco Talos and I'm mainly focused on malware research, threat hunting and tool development. If you want to follow me on Twitter, you can find me at hunterbr72. I'm the author of DDR and I will guide you through the different features of DDR today, the installation process and I will show you some of the best practices, how to use the tool and some of the special cases and caveats which you can see later on in the demos where you might can run into. What is Dynamic Data Resolver? First of all, Dynamic Data Resolver is an instrumentation tool. It is instrumenting the binary so that you can trace all the instructions the binaries executing and it is collecting all kinds of data from strings to register values, memory locations etc etc. It comes with an IDAR plugin which is controlling the backend so you can easily handle everything from this IDAR plugin and you don't need to use the command line tools. You can and I will talk about that later on. DDR comes with the client server architecture so you have the DDR server which is running on the malware PC side. So the PC where you are executing malware and you have the IDAR plugin which is running inside of IDAR on the analyst PC. It is highly recommended to separate these two machines. In theory you can run all of that on one machine but keep in mind that you are executing the malware at the end. So the malware really runs on that machine so you do not want to infect your machine where you have your IDAR installation on be infected with malware. So what can I do with DDR? DDR was mainly built to resolve dynamic values and this is why I have called it Dynamic Data Resolver but it comes with all kinds of other features like the Resolving option you have in DDR. You have the option to resolve certain register values for example. So if you want to know the absolute value of EDI or EBA, EBX or EAX you can just do that with one click. You can also get the pointer to the memory this value is pointing to or even the pointer pointer. And DDR also tries to detect the address which is stored in a certain register if that one points to a certain API call like Virtual Protect. And if that is the case it will also resolve the API call so you can see the human readable name of the function call. After you have run the trace and DDR has all the instruction traces you can highlight the instructions with the color. You can just highlight them depending on how many times they were executed. So you get a pretty quick overview about which basic blocks were executed by the program and how often these basic blocks were executed by the program. As you can see here on the slide if you see a color which is a more warmer color like red or purple you know that this basic block or these instructions were executed many times. So it is likely that it is maybe a decoding routine or something like that. So that already gives you a good clue about what the sample is doing and what parts of the sample are executed and what other parts are maybe not executed. You can also get a table of all the API calls the sample has executed. So you can search through this list. You can search for certain API calls like a virtual alloc or something like that and then you can do a double click on the line and you are jumping to the disassembly code where this API call was called. The same applies for strings. As I mentioned earlier DDR tries to collect all the strings at runtime and it is filling this table with strings and the table is again searchable. So you can look for certain interesting strings like PE for example if you are looking for a PE header and then double click on this line and check out in the disassembly what is going on where this was used. We will see all of that later on in the live demo. Another neat feature of DDR is that there is a smart way to dump buffers at runtime. All you have to hand over to DDR is the size of the buffer the address of the buffer and when or where you want to dump the buffer and we will also see that later on. For example you just have to mark the operands in the disassembly which are storing these informations the other size, the address and at the end where you want to dump the buffer. Unfortunately often malware comes with anti-analysing features and it is not executed like it would be executed on a normal PC if you are running it in a VM for example. So DDR comes with an option to patch the sample at runtime. So for example you can knock out certain instructions or you can toggle the E-flag and manipulate the execution flow. So if there is a conditional branch you can just toggle the E-flag and the conditional branch will do the exact opposite. But again we will see that later on also in the demo. And last but not least you also have the option to completely skip certain functions. You can just mark a function skip it and return a fake return value. So if you have for example a certain function in your malware sample which is checking for virtual machines or for anti-debugging stuff, you can just skip the function and return the value which is telling the sample that it is not getting debugged or that it is not running on a virtual machine. But again we will see that later on in the demo. If IDA and DDR is not enough for you to analyze the sample you can also create an x64 debug script which is automatically executing the sample. So it automatically loads the sample into x64 debug. And it is automatically breaking at that address which you have highlighted in IDA when you have picked this menu point. If you don't like x64 debug you also have the option to create a new executable of the binary with an endless loop at the marked address. So you can mark a certain location or certain address in a site of IDA, pick this menu option and then a new binary is generated which has an endless loop patched at that location. So you can start the binary it starts to loop endlessly and you can attach your favorite debugger to it, restore the bytes and proceed debugging it. Okay, that should be enough for a quick overview about what you can do with DDR. In the upcoming demo we will see all these features in details again. So let's start with the installation. Of course first of all you have to download DDR, you can get it from its repository on GitHub and once you have downloaded it it comes with an installation script and pretty much all you have to do is to execute this installation script and it will guide you through the installation process. Again we will see that later on in the next demo. If you want to stay up to date with the latest versions of DDR you can follow me on Twitter and every time I'm fixing anything or releasing new stuff for DDR I will announce that on my Twitter account. If this presentation is not enough for the information you are looking for you can also find a very detailed blog post about DDR which I have released end of May on our blog which is also describing the different steps, the different features and the best practices and the caveats which you have to be aware of when you are working with DDR. DDR has a client server architecture keep in mind that DDR is instrumenting the binary. So the binary is getting executed at the end. So it is highly recommended to split the analyzing part and the execution part so that you have an analyst PC where your IDA is running on including the plugin and a dedicated malware PC where you are executing the malware sample and analyzing the malware sample. The DDR server is controlling the backend of DDR which is implemented using the Dynamo RIO framework and that one is at the end executing the sample, instrumenting the sample and collecting all the data which is then transferred back to the IDA plugin but we will also see that later on in a demo. Okay so enough theory let's have a look how that looks in the real world. Installing DDR is pretty straightforward. All you have to do is to execute the DDR installer.py script and it is solving all the dependencies for you. After it has downloaded all the dependencies it will ask you a couple of questions about the IDA installation directory the IP address it is supposed to listen on etc etc and after you have done that you can start a local HTTP server or in other words the script is starting an HTTP server for you and then you can move over to the IDA machine and access this HTTP server and download the DDR IDA plugin site of the installation. Then you unzip the file and copy over the content to the traditional IDA plugin directory. That will change in the next release which is coming out very soon and we will move over to the IDA user plugin directory. So that has the advantage that you will not need any administrative rights anymore. Once you have done that you will need to figure out which Python version your IDA installation is using and then you need to tell it to dependencies for this Python version. The request library and the PIFI library and with this you are ready to go and you can move over to the server site again and start the DDR server. After we have seen how the installation works I can give you now a quick walkthrough of the different DDR features which I have mentioned earlier. For this we have a dedicated analyst PC where IDA is running on including the plugin and we have a dedicated machine where we are executing the malware on and where DDR server is running on. Let's move to this malware machine. Once on the malware machine site we are starting the DDR server via the DDR server Python script. When we are starting it there is a little hind that you have to be aware of that there is a caveat with Windows and or Windows command prompt and Python scripts. If you are marking any text in the output window you are freezing the Python application. That means that if the plugin tries to talk to the server now you would run into a timeout. If that happens you just need to hit escape a couple of times or just do a control Z and restart the server if you like. Okay so let's move over to IDA. The first thing you usually want to do is run a trace. A trace is filling all the internal data structures inside of DDR which are necessary for most of the other features. You have two options either to run a light trace or a full trace. A full trace is a trace which is collecting as much information as possible per instruction. For example it is saving all the register values for every single instruction. A light trace is only collecting a subset for these informations but enough information that you can have a look at the API calls for example or at the strings which were traced or to get a source operand. A light trace is usually something which I am running when I start to analyze the sample and if I just want to get an overview, if I just want to highlight the traced instructions for example or if I just want to see the API calls then the light trace is good enough. Later on when I am analyzing a crypto algorithm for example and I need more informations for example all the registers then I am running a full trace but I am only running a full trace for a small address range or for a few basic blocks for example. Because this is really time consuming it is also consuming a lot of memory. So you usually want to limit the amount of instructions which you are instrumenting within full trace. Okay enough about traces. Let's run the light trace and check how that looks like on the DDR server side. So the sample is executed and the dialog box which I have just seen just belongs to the sample code. It doesn't have anything to do with DDR. Don't be confused by that. Once the analyzer is done you can see that the trace log file is written to the same directory where the original sample is located. And you can also see that the temporary trace files were deleted based on the server command and then transferred over to the IDA plugin. So now we can switch back to IDA and we also see this method can switch back to IDA and we also see this message inside of IDA that the light trace was done successfully. So this means that DDR know has all the information it needs and we can execute other features like highlighted trace instruction which is giving us an overview about which basic blocks were executed or which instructions were executed. Okay so let's move to the next feature. You can knock out instructions at run time. So if you have certain instructions which you want to get rid of like the dialog box which we have seen earlier you can just mark these instructions and you go to the patch menu in DDR and then next time you execute the sample so for example you run a new trace then these instructions are knocked out they're not getting executed anymore and you can see here that it is responding much faster because we didn't have the pop up of the dialog box and the sample immediately proceeded with execution. Okay the next feature which I would like to show you is you can use the dynamic values which were collected by the trace. First we are doing a trace again. This time we are just doing a trace over a couple of instructions. You're picking full trace for marked address range and once this is done we have all the values from these instructions inside of the database. So we can just go to get value for source operand including the value for rax in this case or we can just get the values from memory pointers like you can see here or all kinds of other informations DDR has collected. Next nice feature is that you can collect all the strings and API calls at run time. You can show both of them via tables where the DDR menu is located. So if we are looking at the strings for example this is a list of all the strings which we have collected at run time and of course you can also search for something in there like PE for example and if you are double clicking on the line then you are jumping to the line in the assembly where it is used. You can also have a look at the API calls which were executed at run time and again the same strings you can search for something and double click on it and then you see where it is used inside of the code. You have seen earlier that you can manipulate the code flow by nipping out instructions but there are also other options inside of DDR which are manipulating the code flow. The next one which I would like to talk about is the option to toggle the flexor. So for example if we have a code like this where we have a conditional jump and a comparison before then we can toggle the E-flag at the jump. In this case you have to know that EAX can never be bigger than 5. So at least in theory this jump should always be taken in this code and the program should print out main A is not greater than 5. If we want to manipulate that we can just mark the GLA instruction, do a right click and go to the patch menu inside of DDR. Inside of the patch menu we pick toggle E-flag. In this case we have to toggle the SF-flag and once this is done we can now just run the sample if we want. So for example again over the patch menu if we pick that one then the sample is just getting executed but we could also use any other feature of DDR running a trace or doing a dump which we will see later on. All these patches which I have applied will work for all the DDR features. Once we executed it then we can move over to the DDR side and check the output of the file. Sorry of the executable. So here you can see that the patch worked and the program printed out A is greater than 5 and this should never happen. The last option you have is you can skip functions at runtime. So for example if we have my function 1 here in this case and maybe something which is doing some anti-analysing, anti-debugging stuff you can just skip it and you can fake the return value. You are just marking the first instruction in the function and you are going again to the patch menu skip function at marked address at runtime and you hand over the faked return value and that's it. Now you can execute the sample again moving over to the DDR server side we see that the sample is getting executed and in the output of the sample we should see that the my function 1 output is gone because the my function 1 is not executed anymore. Another main function of DDR is that you can dump buffers at runtime and you can do that in a smart way. Later on the string will be copied into this buffer which we are going to dump. So remember that for later. So for example if you have a function like virtualalloc all you have to do is you have to mark the operand which is storing the size of the buffer now I get buffer size and the next thing is you mark the operand which is storing the address of the buffer which you are going to dump and get buffer address and last but not least the final step is you mark the instruction or the location where you want to dump the buffer. So use marked address to dump buffer to file. That's it. Now you can go to the dump menu and execute the sample and the buffer gets automatically dumped at runtime. Once it is dumped it is transferred over to Ida and you can store it somewhere on disk. Here you can see that it is the buffer which I have mentioned earlier where the program has copied the PE string into. If you want to debug the sample inside of x64 debug you can also generate x64 debug scripts which are automatically setting a breakpoint at the location which you have. So once you have generated the script you can load it into x64 debug. All you have to do is to run the script it will automatically start the sample and break at the breakpoint which you have highlighted in Ida. So here we have reached the breakpoint the script has finished and now you can proceed debugging in x64 debug. Last feature which I would like to show you is how to create endless loops in binaries. So if you want to create an endless loop you can just mark the line where you want to create the loop and then you select create executable with loop at marked address. Now DDR is creating a patchable with loop at marked address. Now DDR is creating a patched binary and you can move over to the DDR server side and you will find a patched binary in side of the samples directory. Now you can start this binary just double click on it and at a certain point we are reaching this endless loop. So now we can attach our debugger to it and proceed debugging the sample. So after pausing the sample of course the first thing you have to do is you have to replace the patched bytes the patched bytes of the endless little help in the DDR server output to see what kind of bytes you have to patch.  So when we are proceeding to debug you see that this changed to the original bytes and now you can just proceed debugging like usual. That's it. Okay, so this was the installation and the feature work through of DDR. Let's move on and have a look at some of the special cases and of course the best practices. The better you know DDR the more efficient you can use DDR. And as usual the easiest is to watch a quick live demo about it. When I start analyzing samples I like to run a quick light trace. Light trace is only executing 20,000 instructions by default. Now you can change this default value. If you are running a light trace you can probably set that up to 200,000 but this is in this case for this sample not necessary so we can leave the default value. Once the light trace is executed we can highlight the trace instructions to see which basic blocks were actually executed. This was pretty quick in this case so let's see what's going on. Highlight trace instructions and we see that there are only four basic blocks which were actually executed. So it seems to be that there is some really analyzing checks going on. So let's go into the last function which might be responsible for this check. So when we are scrolling down a little bit we see that it seems to be that this function is dynamically resolving the get-native system in for API call. It's using get-process address. We see that pretty often in malware samples. Then it is subtracting the address in this variable and a bit later on it is subtracting 10 from this address. And a little bit below we see that this value is pushed as an argument to the next function. So it seems to be that the first argument of this function is this get-native-system in for API call function address minus 10. So when we are looking at the first argument here we see that it is executing a couple of mathematical instructions and it seems to be that it is just adding 10 to it so it has restored the original address and it seems to be that it is just calling the get-native-system-info API call here at that point. Unfortunately in real malware this is often much more complicated. So in real malware we often see that these calculations are distributed all over the place and they are heavily obfuscated. So it is often very difficult to figure out what is actually called at this point. With DDR that is much easier. You can just do a right click and you can get the value of this function pointer. Just pick get-value for pointer and source operand. And then you see the value which was used at runtime. So it is confirming what we assumed get-native-system-info is called. With this information we can now go one level up and we can change the name of this argument to function pointer get-native-system-info minus 10. And we have also seen earlier in this function that there was one parameter pushed and this is the second argument of this function. So if we are looking at the get-native-system-info we see that this is actually a pointer to the system infrastructure which is storing all the system informations. So again we can go to the function above and we can find the second argument here and we can also rename it to something like system-info or whatever you like. As far as this is a stack variable which is pointing to a structure, we can also do some housekeeping and quickly assign the right structure to it. So that makes it a little bit easier when we are proceeding the analyzers to see what's going on. So here we can see that here is actually a comparison between the number of processors and three. With a closer look we see that if the number of processors of the machine where the sample is running on is smaller than 3, then we are just printing out a likely virtual machine detected. So if it has two or less processors the sample assumes that it is running on a virtual machine. If it is more than two processors it is returning 0. And again if we go one level up we can see here that it is comparing EAX and only if it is 0 then it is proceeding with the rest of the Melba code. If not it is just exiting. Let's rename the function quickly to something like the mCheck and let's proceed analyzing. So of course we are also interested in the rest of the code and to make sure that we can execute it on a virtual machine we can just toggle the eFlex like you have seen before. Now in this case it jumps 0 so the 0 flex are fine. So let's run the trace again and wait for the results. Okay so I've cheated now a little bit and fast forwarded the video we run into a timeout. So we are seeing this warning message here and it is telling us that the response from the DDR server took too long. By default the plugin waits for 30 seconds to get the results from the DDR server, the trace for example. And if you like you can change this behavior here in the API timeout. You can increase the timeout for example to 60 seconds or to 100 seconds or whatever you think works and then the plugin waits for a longer time. So you've seen earlier that you can also configure the number of instructions for example which are supposed to be analyzed. You can play with these two values a little bit of course if you're increasing the number of instructions much more data will be collected and the files which are going to be exchanged are also much bigger. So sometimes it helps to increase the timeout to do these kind of long traces. But nevertheless make sure that you're not increasing the number of instructions to a too high value. Keep always in mind that it is also increasing the file size of the data which is collected. So coming back here to our issue that it timed out we can for example now look over to the server side and we can check if there was some internal error for example there could be a bug inside of DDR which caused a crash for example or there could be some other reason a super endless loop or whatever and a sleeper whatever. And we see here that the analyzes run for 60 seconds so it seems to be that it was successfully executed. When we are now going back to EIDA we can proceed with the analyzes of the malware to get an idea about what happened. And usually you would know check these instructions what's happening of course I'm not doing that in detail here in the demo and I know the result and the reason for the timeout in this case is a sleep timer. So you have a sleep timer here which is actually waiting for 60 seconds and of course that is more than the 30 seconds and we haven't reached the maximum number of instructions at that point yet. So the DDR server side is still trying to analyze the sample but there are no new instructions but before this sleeper is not over so this means that the analyzes are still going on on the server side but the plug-in runs into the 30 seconds timeout. So we could now increase the timeout for example and just wait for a little bit longer or again we can just here knob out these instructions and run it again. I don't like to wait so I prefer using the knob out functionality and now we are running the trace again and now it should be a little bit quicker. So light trace done and now we can clear the old highlighted instructions clear highlighted instructions and we can highlight it again and now we can see the new path with all our patches which we have applied. Now you see that we have manipulated the VM check here even if it has detected the VM bear, nevertheless we toggled the infleck here and we are going this way and now it is checking here if its name is evilmalve.exe and if that is not the case then the sample is going this way and a quick summary of what's happening here is copying itself over to the temp folder and then finally here after the sleep it is creating the process and starting another instance of itself and just from this other directory. So this is the reason why we are seeing that we are reaching here this exit call and the sample seems to be or the execution of the sample seems to be stopped at that point. In reality it has started the new instance and the new instance is running under this name so it will now go this path and it will proceed to execute the rest of the code. This should be enough for this sample so let's move on to the next one, actually one which we found during a recent appetitum campaign. It is an executable which looks like an XML file but as you know if you run that on the command line it will execute it like any other former executable. To get an overview about what it is doing as usual we are just running a quick light trace with ddr. When we are moving over to ddr we suddenly see what that the window disappeared. So it seems to be that maybe the process was killed or something like that, interesting. So we are moving back to Ida and we suddenly see that the light trace was nevertheless successfully executed. It seems to be that the ddr process is still running in the background. So what's going on here? To get an idea it's always a good idea to check the API calls which were executed and when we are looking at those we see that there's a couple of initalization going on and stuff like rebuilding the IRT for example a lot of get process address calls and after that we suddenly see oh there is a show window API call. That looks interesting because with show window you can manipulate the window and when we are looking into the disassembly we see that it is using get console window to get the handle of its own window and then it is executing show window and show window is using ESI for the command show parameter and ESI is cleared right before. So we can be pretty sure that ESI is zero in this case but even if it would be a more complex function in a different sample for example of course we can always use ddr to get an idea about what this value is here in our case zero obviously. So it is handing over zero to show window and if we are having a closer look to the show window function we will see that the command show parameter is offering a couple of different options and if it is zero it is just hiding the window from the desktop so we have solved the issue why the command window suddenly disappeared. It was not killed into the background. So this is one of the examples how you can pretty quickly analyze what actually happened with your sample and now you could either leave it like it is in this case because it doesn't hurt or if you still want to see the window you just go ahead and you kill these instructions because you don't need them for anything else. You can just knock them out about marked instructions and then we are restoring the snapshot on the other side on the ddr server side and once it is restored we can just run the sample again just do it light trace again and now we can see that it is running normally like before but it is not hiding the window anymore because we have knocked out these instructions and we are done and we can proceed with our analysis. Back to the presentation another special case which I would like to talk about is if you want to analyze the sample in an air-gapped environment so for example if the sample is doing excessive anti-VM bed checks or if you have to disable the networking for any reason there are probably many cases why you want to analyze the sample on an air-gapped system you can do that because the engine of ddr is implemented in a way that it is a command line tool and it is heavily leveraging the Dynamo-Rio framework to do all the instrumentation so at the end the ddr server script is just executing this command line tool to inject the ddr DLL into the sample the ddr DLL is the engine which is doing all the analyzes which is saving all the traces and the registers and so on and if you are running this command line tool via dr run Cclient DLL and the sample to instrument you will get a JSON file back or actually you are getting two JSON files back for the instruction trace and one for the API trace these JSON files are looking like this so they have all the informations per instruction in it so all the registers or the values of the registers at the point of the instruction the eflags, the disassembly etc etc plus the memory location which might be interesting and so on and this is a JSON file which is getting transferred over to the IDAR site and which is the IDAR plugin reading to fill in its data structures and with this file you can then use the plugin like you have seen before you have seen earlier in the command that you have to hand over a configuration file and you will find in the docs directory of the github repository a sample configuration file which is heavily commented and gives you an idea about what kind of commands you can write into this configuration file we will see in the demo you can also use the output of the ddr server script to get an idea about what's going on and what kind of values you can use so for example you can just generate a certain command via the plugin and then you can check the generated configuration but again we will see that later on in the demo so talking about the demo let's have a look at it and see how that works on the command line so when you are running the command line tool the first time you can cheat a little bit by looking at the server output the ddr server is printing out the command which it is actually executing this is the command and the configuration which belongs to the command which was automatically generated by either plugin so you can start with using the GUI and then you can have a look at the configuration file and the command line and this gives you probably a good idea how these things are actually working and for the details again you have the documentation in the docs directory of the github repository so let's just run this again and once it is finished we see that it has written all these trace files to the samples directory let's move over to the samples directory and we see that we have all these generated traces here but there are also further files like the ddr process trace and the ddr process trace is a file which is logging all the processes which were started by the sample and pretty much the same but for threads are these threads files they include the information about which threads the certain processes have started so if we are looking at the processes file for example we see that the original sample has executed a second process the evilmalve.exe and ddr is following all the threads and processes which the original sample is creating so we have seen earlier in IDAR the trace which was imported for the main thread and for the main process we haven't seen the second process in IDAR so far but the trace was generated so we can go back to IDAR and we can import this one and then we have all the instructions which were executed by the process evilmalve.exe the second instance of the exe file and let me show you how that works okay so we are back in IDAR and you hopefully remember the sample which we have looked at earlier the buffer test dot one the one which was checking if its name was evilmalve.exe and if that is not the case it is copying itself to the temp folder and executing itself under this name again and you remember that we were only following the main process here and we were able to highlight the instructions down to the point where the initial process exited but of course we are also interested in the second part what happens with the second instance and what kind of code is the second instance executing one thing we could do of course is we could just manipulate the code again like we've done before or now we are importing these files which we have just generated so we can clearly highlight the instructions and we are using the low ddr trace button to go to the directory where we have imported these traces which we have seen earlier so now I am interested in the one of evilmalve.exe so I am loading this one for the traced commands and I am loading this one for the API calls so now we have successfully imported these traces one for the API calls and one for the instructions and now we can use ddr like we've done it before and you see that the second instance which is running under evilmalve.exe is of course going this path and now we can proceed analyzing these parts and look what it is doing like we've done before get source value or whatever helps us to understand what this sample is doing the last thing which I would like to mention is that you should really keep in mind that it is good practice not to run traces for too many instructions, keep in mind that stopping at every instruction and collecting all the registers and all the memory information of course it takes a lot of time and consumes a lot of memory so it's usually good practice to just mark the basic blocks you are interested in for example if we are just interested in the values of these two basic blocks it is usually a good idea to just select them at basic blocks to list and this one select at basic block to list and you can see that it was successful here and then run the trace just for the basic block list and it is done, that is much faster you don't have to wait for too long and you're not creating gigabytes of files just keep in mind that if you are doing that that you now only have these two basic blocks in the database so all the others are not in the database at the moment which means that if you try to get a value from here then of course you are running into an error it's not in trace it can be a little bit confusing in the beginning if you don't think about it but usually you are getting pretty quickly used to that and now you can analyze the functions which you are actually interested in get source value or whatever you are looking for that's it, so you have seen that DDR is not replacing your brain but nevertheless it speeds up a lot of reversing tasks and it is usually a pretty big help in analyzing malware samples with this I'm done for today and I'm giving back to the folks from the blue team village


Introducing Fingmao. The introduction of Fingmao finally gives us something in fault that no one asked for. A two shot assassin that has more survivability than a full kit tank. You know what's more annoying than Count us slipping to you and deleting you with three abilities? Fingmao doing it with two and then shielding his entire goddamn health bar so we can keep going.  They're like, he has meth abs, be warned. Reaping Dash is the new spam bush. Remember how annoying it was when Chimera would just repeatedly ambush? Well with Fingmao it goes further, hits harder, and resets on kill. It's like having a Dark Souls roll. You just keep moving as long as you have enough blue bar.  Hamstring. It's a, I mean, yeah it's a thing you can do. Guardian Shield. This is the problem. Fingmao's shield explodes when it expires and deals AOE damage and it's freaking huge.  The shield size scales off attack power so the harder you hit, the bigger hits you can take. This defies all video game logic. Everyone since the original Street Fighter 2 knows that you must have balance. If you hit hard as fuck, you're squishy. If you can take a lot of damage, then you should either not hit very hard or be super slow. Fingmao is an unholy amalgamation of Chun-Li, Zangief and Ryu, and all of his attacks are fierce. Fingmao's ultimate is called Imperial Sentence.  Two resets on one overpowered hero? Why not?  This is an ability that the enemy team's Fingmao will have perfected while you get to watch your Fing use it on a full health steal. But how much range does it have? Enough. It always has enough. Counter Fingmao the same way you counter every other overpowered assassin, by shutting him down early. Yeah, that's really easy to say, but it's kind of hard to shut him down when the only time I see this fucker is when I'm a split second away from taking like 3 million damage to the face.  I don't want to hear it.  Learn to play him or lose in fault today. Get 28 kills, but still complain about mana problems on Fingmao today. Right click to add Severog's entire health bar as a shield on Fingmao today. Special shout out to channel members Foolish Bloodhunter Jelly Knees Meow, mixed for men Stunt, Farith, and Raven.