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 enjoyed reading the blog

I enjoyed reading the blog above. Thanks for sharing this information.

Me too! It's very educational

Me too! It's very educational and i'm glad to learn something new again.

www.tampadrywallcompany.com

Thank you for providing an

Thank you for providing an example of Java method and delve into the Dalvik bytecode to illustrate how this lack of type information can pose difficulties for an abstract interpreter like Daneel. | www.drywalldc.com

It's great that you've given

It's great that you've given credit to Rémi Forax for the implementation of the abstract interpreter and the method rewriter. Your explanation helps shed light on the process and challenges involved in transforming Dalvik bytecode using an abstract interpreter like Daneel.

I'm so happy and impressed

I'm so happy and impressed with the details! Thanks for posting

I'm so happy and impressed

I'm so happy and impressed with the details! Thanks for posting <a href="https://careers.tql.com/us/en/entry-level-jobs-indianapolis">best entry level jobs Indianapolis</a>

I am really thankful to you

I am really thankful to you for giving me blog commenting sites. It has been useful.

During bytecode

During bytecode transformation processes like optimization or analysis, the lack of explicit type information can pose challenges.

Thank you for this amazing

Thank you for this amazing blog!

https://treeserviceclarksville.net

As the Dalvik bytecode format

As the Dalvik bytecode format evolves, the challenges of working with untyped instructions will likely be addressed.

I'll save this information!

I'll save this information! Thank you so much

Golden Triangle Tours offers

Golden Triangle Tours offers the best-selling Golden Triangle tour packages in India.

So far you have a good

So far you have a good content! Thanks

Have you ever heard of

Have you ever heard of https://www.celebheightwiki.com/ - the famous website for celebrities information?

That sounds interesting!

That sounds interesting! Understanding the challenges of untyped bytecode can be crucial when working with Dalvik.

I love this blog, I really

I love this blog, I really appreciate this so much.

Thank you for some other

Thank you for some other informative website.
Where else may I get that type of info written in such a perfect means?
I've a mission that I'm simply now running on, and I've been on the glance out for such info.

I just wish to provide a

I just wish to provide a enormous thumbs up for any excellent information you have here about this post. I will be coming back to your blog post for further soon.

You have a great data! Thanks

You have a great data! Thanks

Indeed!

Indeed!

Thanks a lot for sharing this

Thanks a lot for sharing this with all of us you actually know what you’re talking about!

"very informative article!!!

"very informative article!!! thank you so much!
"
https://treeservicetampafl.net

I absolutely agree with you!

I absolutely agree with you!

Resin-bound driveways require

Resin-bound driveways require a minimum of maintenance. Regular power washing will help keep them looking shiny and new. Installing a resin-bound surface on your driveway is a quick and hassle-free process, and it provides superior traction for cars and pedestrians alike. This material is also wheelchair-friendly, making it the ideal choice for anyone with disabilities. In addition to being durable, resin-bound surfaces require minimal disruption and will last many years.

Wew, this is so cool! Thanks

Wew, this is so cool! Thanks for sharing

This is worth trying!

This is worth trying!

I really enjoyed reading your

I really enjoyed reading your post. It was well-written and engaging https://www.drywallcontractorrichmondbc.com/burnaby-drywall-installation...

Cheers for more.

Cheers for more.

Thanks a lot for sharing this

Thanks a lot for sharing this with all of us you actually know what you’re talking about! https://partybusnewbrunswick.com/

Thank you very much for this

Thank you very much for this wonderful topic

No regrets about using this

No regrets about using this program!

Thanks for the advice.

Thanks for the advice.

I’ve bookmarked your site,

I’ve bookmarked your site, and I’m adding your RSS feeds to my Google account.

The same thing i did before!

The same thing i did before! Now, It's still a big help to me.

Thanks for an informative

Thanks for an informative insight into the challenges and techniques of type inference for Dalvik bytecode.

Nice article, waiting for

Nice article, waiting for your another

This is really helpful.

This is really helpful.

Really nice article and

Really nice article and helpful me

I wish I knew more about

I wish I knew more about Java, thus I value it when people are willing to share their knowledge with me.

Great Post! I learned a lot

Great Post! I learned a lot from this, Thank you!

I thik this is very helpfull

I thik this is very helpfull post

Please keep up the good work!

Please keep up the good work!

Great job for this comment!

Great job for this comment!

Very informative content.

Very informative content. Thanks.

Do you personally recommend

Do you personally recommend this?

What a great piece of

What a great piece of article!

Exactly! I love it.

Exactly! I love it.

You presented your ideas and

You presented your ideas and thoughts really well on the paper.

Many many thanks to you!

Many many thanks to you!