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.

Really useful source of

Really useful source of information. Thanks for sharing

Here at Bel Air Tow Truck, we

Here at Bel Air Tow Truck, we strive to provide a great towing experience, and we do not settle for less. We offer a variety of services that will allow you and your company, or family to rest assure they are getting the best rate as possible.
https://belairtowtruck.com/

Thanks for this great

Thanks for this great information you've shared. https://www.sugarcreektowtruck.com/

This is very refreshing!

This is very refreshing! hope to read another kind of article like this.

https://www.northshorecommercialsolar.com.au

Thanks for sharing this

Thanks for sharing this one https://www.kansascitymotowingservice.com/

I am glad to read the

I am glad to read the information you shared https://www.kansascitymotowtruck.com/

I like this

Northern Virginia Equipment

Northern Virginia Equipment Transport is a local service that you can trust to get your large valuable assets to where they need to be.
http://novaequipmenttransport.com

How nice, great

How nice, great post! https://www.bluespringstowtruck.com/

Really interesting article, I

Really interesting article, I hope you produce more of it. Thank you for sharing. https://www.treeserviceschelmsford.co.uk

I agree with you the content

I agree with you the content was very informative. Thanks for sharing.[URL=https://www.treeserviceshighwycombe.co.uk/]Tree Surgeon High Wycombe[/URL]

Love this thread, thank you

Love this thread, thank you for sharing https://greensborotowtruck.com/

Thanks for sharing this great

Thanks for sharing this great stuff here https://fayettevilletowtruck.com/

Glad to check this

Glad to check this site https://durhamtowtruck.com/

Thanks for this great post

Thanks for this great post you shared http://www.charlotteareatowingservice.com/

Today, Culpeper Tow Truck is

Today, Culpeper Tow Truck is one of the top towing companies in the state and can provide a wide range of towing and roadside assistance services.
http://culpepertowtruck.com/

Delray Beach Towing Service

Delray Beach Towing Service is the premier towing company serving Delray Beach, FL and the surrounding region.
https://delraybeachtowingservice.com

Good job. Very informative

Good job. Very informative article. https://ketteringtowingservice.com/

Awesome site to check

Awesome site to check in. https://daytontowingservice.com/

Thank you for taking the time

Thank you for taking the time to publish this information https://athenstowtruck.com/

Thank you for sharing. This

Thank you for sharing. This content has a detailed information https://towinglexington.com/

I am appreciating it very

I am appreciating it very much! http://www.towingcolumbiasc.com/

This is very well

This is very well written https://charlestontowingservice.com/

Thanks for the valuable

Thanks for the valuable information and insights you have provided here. https://winstonsalemtowtruck.com/

This is obviously a one great

This is obviously a one great post. https://raleightowtruck.com/

Impressive interpretation!

Impressive interpretation! Good job!

This is really exactly what

This is really exactly what I'm looking for! Thanks a lot!

-Grant

Vienna Private Property

Vienna Private Property Parking Management provides the best management services in Vienna and no competition has been able to match.

https://viennaparkingmanagement.com/

To me this a is very nice

To me this a is very nice site. https://hamptontowtruck.com/

Content is really nice, it is

Content is really nice, it is well written.

tHANKKYOUR

tHANKKYOUR

Content is really nice, it is

Content is really nice, it is well written. https://towtruckchesapeake.com/

I agree with you the content

I agree with you the content was very informative. Thanks for sharing.
https://www.bakersfield-handyman.com/

It is very informative. I

It is very informative. I agree with you.
https://www.chicocatreeservice.com/

Nova Cash For Junk Cars began

Nova Cash For Junk Cars began as a small family business in North Virginia. We want our customers to feel that they can recommend us to their family and friends.
https://novacashforjunkcars.com

The team at Fredericksburg

The team at Fredericksburg Tree Service are true experts of their craft.
https://treeservicefredericksburg.com

Albany Tow Truck is happy to

Albany Tow Truck is happy to service the greater Albany, Schenectady and Troy with our full fleet of tow and roadside assistance vehicles. We are proud of our safe work place.
http://www.asttowing.com/

The team at Independence Tow

The team at Independence Tow Truck are proud to serve a large service area. That means that we have more trucks on the road and more people that we can help out in their time of crisis.
https://independencetowtruck.com

The team at Independence Tow

The team at Independence Tow Truck are proud to serve a large service area. That means that we have more trucks on the road and more people that we can help out in their time of crisis.

here in Hialeah Tow Truck, we

here in Hialeah Tow Truck, we have been proud to service Hialeah, FL and the surrounding area for years.

https://hialeahtowtruck.com/

I agree, this is a very well

I agree, this is a very well written article. Thanks so much for sharing. https://www.petesappliancerepair.ca

Thanks for this information.

Thanks for this information. I appreciate it https://charlottesvillevatowtruck.com/

Thanks for sharing this! This

Thanks for sharing this! This is very insightful! https://sanfordtowingservice.com/

This is an impressive and

This is an impressive and informative site. Keep it up https://orlandofltowtruck.com/

Thanks for sharing this! This

Thanks for sharing this! This looks pretty informative! https://kissimmeetowtruck.com/

Fredericksburg Towing Service

Fredericksburg Towing Service is a full service towing, rescue, and recovery business serving the city of Fredericksburg and all of the surrounding areas of Virginia.
http://fredericksburgvatowing.com

https://viennaequipmenttransp

https://viennaequipmenttransport.com/

Vienna Equipment Transport is a company providing equipment transport services in Vienna, Virginia.

I’m really impressed with

I’m really impressed with your article https://winchestertowtruck.com/

I agree, this article is

I agree, this article is quite impressive. Thanks for sharing! https://www.joshbowie.com

Keep sharing great post, I

Keep sharing great post, I like them. https://virginiabeachtowtruck.com/