Daneel: Type inference for Dalvik bytecode

In the last blog post about Daneel I mentioned one particular caveat of Dalvik bytecode, namely the existence of untyped instructions, which has a huge impact on how we transform bytecode. I want to take a similar approach as last time and look at one specific example to illustrate those implications. So let us take a look at the following Java method.

public float untyped(float[] array, boolean flag) {
   if (flag) {
      float delta = 0.5f;
      return array[7] + delta;
   } else {
      return 0.2f;
   }
}

The above is a straightforward snippet and most of you probably know how the generated Java bytecode will look like. So let’s jump right to the Dalvik bytecode and discuss that in detail.

UntypedSample.untyped:([FZ)F:
  [regs=5, ins=3, outs=0]
   0000: if-eqz v4, 0009
   0002: const/high16 v0, #0x3f000000
   0004: const/4 v1, #0x7
   0005: aget v1, v3, v1
   0007: add-float/2addr v0, v1
   0008: return v0
   0009: const v0, #0x3e4ccccd
   000c: goto 0008

Keep in mind that Daneel doesn’t like to remember things, so he wants to look through the code just once from top to bottom and emit Java bytecode while doing so. He gets really puzzled at certain points in the code.

  • Label 2: What is the type of register v0?
  • Label 4: What is the type of register v1?
  • Label 9: Register v0 again? What’s the type at this point?

You, as a reader, do have the answer because you know and understand the semantic of the underlying Java code, but Daneel doesn’t, so he tries to infer the types. Let’s look through the code in the same way Daneel does.

At method entry he knows about the types of method parameters. Dalvik passes parameters in the last registers (in this case in v3 and v4). Also we have a register (in this case v2) holding a this reference. So we start out with the following register types at method entry.

UntypedSample.untyped:([FZ)F:
  [regs=5, ins=3, outs=0]               uninit uninit object [float bool

The array to the right represents the inferred register types at each point in the instruction stream as determined by the abstract interpreter. Note that we also have to keep track of the dimension count and the element type for array references. Now let’s look at the first block of instructions.

   0002: const/high16 v0, #0x3f000000   u32    uninit object [float bool
   0004: const/4 v1, #0x7               u32    u32    object [float bool
   0005: aget v1, v3, v1                u32    float  object [float bool
   0007: add-float/2addr v0, v1         float  float  object [float bool

Each line shows the register type after the instruction has been processed. At each line Daneel learns something new about the register types.

  • Label 2: I don’t know the type of v0, only that it holds an untyped 32-bit value.
  • Label 4: Same applies for v1 here, it’s an untyped 32-bit value as well.
  • Label 5: Now I know v1 is used as an array index, it must have been an integer value. Also the array reference in register v3 is accessed, so I know the result is a float value. The result is stored in v1, overwriting it’s previous content.
  • Label 7: Now I know v0 is used in a floating-point addition, it must have been a float value.

Keep in mind that at each line, Daneel emits appropriate Java bytecode. So whenever he learns the concrete type of a register, he might need to retroactively patch previously emitted instructions, because some of his assumptions about the type were broken.

Finally we look at the second block of instructions reached through the conditional branch as part of the if-statement.

   0009: const v0, #0x3e4ccccd          u32    uninit object [float bool
   000c: goto 0008                      float  uninit object [float bool

When reaching this block we basically have the same information as at method entry. Again Daneel learns in the process.

  • Label 9: I don’t know the type of v0, only that it holds an untyped 32-bit value.
  • Label 12: Now I know that v0 has to be a float value because the unconditional branch targets the join-point at label 8. And I already looked at that code and know that we expect a float value in that register at that point.

This illustrates why our abstract interpreter also has to remember and merge register type information at each join-point. It’s important to keep in mind that Daneel follows the instruction stream from top to bottom, as opposed to the control-flow of the code.

Now imagine scrambling up the code so that instruction stream and control-flow are vastly different from each other, together with a few exception handlers and an optimal register re-usage as produced by some SSA representation. That’s where Daneel still keeps choking at the moment. But we can handle most of the code produced by the dx tool already and will hunt down all those nasty bugs triggered by obfuscated code as well.

Disclaimer: The abstract interpreter and the method rewriter were mostly written by Rémi Forax, with this post I take no credit for it’s implementation whatsoever, I just want to explain how it works.

I personally like your

I personally like your post https://waynesborotowtruck.com/

I am glad seeing this nice

I am glad seeing this nice website. https://stauntontowtruck.com/

Our new s22 ultra aluminum

Our new s22 ultra aluminum case has even more screen, corner, and camera protection without adding bulk, so it still feels slim and fits easily in your pocket, but you don't have to worry about drops of up to 6 feet!

https://www.redpeppercases.com/products/galaxy-s22-ultra-shockproof-armo...

You did a great job on this

You did a great job on this excellent site https://roanokevatowtruck.com/

Its a really nice and useful

Its a really nice and useful piece of information.I am glad you shared. many thanks

Excellent website, lots of

Excellent website, lots of useful information here. many thanks for sharing

Trying to get my head round

Trying to get my head round float values, this article really helps.
Thank you you.
https://www.treeserviceschelmsford.co.uk

Great job for publishing such

Great job for publishing such a beneficial web site https://richmondtowtruck.com/

I really like all the points

I really like all the points you made. https://petersburgtowtruck.com/

Possibly the best person to

Possibly the best person to ask about the topic. Would you agree to them.

Valuable information,

Valuable information, awesome! https://norfolktowtruck.com/

Well written

Informative! This is

Informative! This is great! https://lynchburgvatowtruck.com/

It is nice seeing this page,

It is nice seeing this page, informative one! https://harrisonburgtowtruck.com/

Only a few bloggers would

Only a few bloggers would discuss this the way you do. Thanks for sharing, Very educating.

This is very informative and

This is very informative and practical content. Looking forward to more amazing articles like this. Thanks for sharing.

The best approach to solve

The best approach to solve this issue.this solution was really helpful.

This post was very helpful, I

This post was very helpful, I agree!

It is the intent to provide

It is the intent to provide valuable information and best practices, including an understanding of the regulatory process. <a href="http://www.nikoboehm.de/g-stebuch/index.php">Tony Scott Dietrich</a>

Nice to read your article! I

Nice to read your article! I am looking forward to sharing your adventures and experiences.

Thank you for sharing such

Thank you for sharing such valuable information, I can't wait to share this with all of my work colleagues.

I was surfing the Internet

I was surfing the Internet for information and came across your blog. I am impressed by the information you have on this blog. It shows how well you understand this subject.
buying and selling real estate https://raleigh-real-estate.sitey.me/blog/post/65022/real-estate-agents-...

I had no trouble navigating

I had no trouble navigating through all the tabs and the information was very easy to access. I found what I wanted in no time.

Now I know v0 is used in a

Now I know v0 is used in a floating-point addition, it must have been a float value.

I really treasure your piece

I really treasure your piece of work, Great post. house rental search tips https://butterflylabs.com/rental-search-tips-and-tricks-from-real-estate...

Control-flow are vastly

Control-flow are vastly different from each other, together with a few exception handlers and an optimal register re-usage as produced by some SSA representation.

Keep in mind that at each

Keep in mind that at each line, Daneel emits appropriate Java bytecode.

Dalvik passes parameters in

Dalvik passes parameters in the last registers (in this case in v3 and v4). Also we have a register (in this case v2) holding a this reference. So we start out with the following register types at method entry.

I must say that I am

I must say that I am impressed with your site. I had no trouble navigating through all the tabs and the information was very easy to access. I found what I wanted in no time.
Great job.

I agree, this website is very

I agree, this website is very easy to navigate. Glad I found it!

So whenever he learns the

So whenever he learns the concrete type of a register, he might need to retroactively patch previously emitted instructions, because some of his assumptions about the type were broken.

The abstract interpreter and

The abstract interpreter and the method rewriter were mostly written by Rémi Forax, with this post I take no credit for it’s implementation whatsoeve.

Regards for this terrific

Regards for this terrific post, I am glad I discovered this site on yahoo. real estate interest rates https://www.imagup.com/interest-rates-affect-real-estate-market/

great information bytecode!!

great information bytecode!! I like it !!
<a href="https://www.atticinsulationsilverspring.com/">Read More</a>

You made some decent factors

You made some decent factors there. I looked on the internet for the problem and found most individuals will go along with with your website.Anthony Dietrich https://www.hotfrog.com/company/1307313258409984/anthony-dietrich/gaines...

At method entry he knows

At method entry he knows about the types of method parameters. Dalvik passes parameters in the last registers (in this case in v3 and v4). Also we have a register (in this case v2) holding a this reference. So we start out with the following register types at method entry.

Now I know v1 is used as an

Now I know v1 is used as an array index, it must have been an integer value. Also the array reference in register v3 is accessed, so I know the result.

Wow how good is this. Thank

Wow how good is this. Thank you from https://www.goldcoastbifolddoorpros.com.au

So glad I found this! Thanks

So glad I found this! Thanks for sharing from both https://www.centralcoastshowerscreens.com & https://www.geelongshowerscreen.com.au

Love this thread! Thank you

Come and check this out for

Come and check this out for wonderful reviews about carports design. You will be amazed!

This is very interesting! I

This is very interesting! I would love to know more about it.

Actually I believe the whole

Actually I believe the whole text for Cody and Phil got swapped. Or the photos got swapped. One or the other.

I am building a 24x18ft

I am building a 24x18ft carport with 8in c channel spaced 4.5ft and spans the 24ft. I am using 2 1/2in oilfield pipe as the 4 corner posts and it will have a metal roof. It will stand aprox 8ft to top of structure. Do I need to add more support posts or can the 4 post handle the weight. The posts will have .5in plates welded to bottom with bolts going into concrete slab. Thanks to anyone with some advice. And of you need anymore info just lmkhttps://www.atticinsulationsilverspring.com/

This is such a great blog.

This is such a great blog. Thank you for sharing your talent with everyone. You are an inspiration. Keep posting!

It’s important to keep in

It’s important to keep in mind that Daneel follows the instruction stream from top to bottom, as opposed to the control-flow of the code.

Such a high standard post!

Such a high standard post! Thanks from https://www.sydneybifolddoorpros.com.au

Thanks. I really like it !!

Thanks. I really like it !!

Wow! Thanks for the great

Wow! Thanks for the great explanation of how this bytecode works.

Much appreciated. Cheers!

Awesome information!

Awesome information!