search

radareorg / radare2

UNIX-like reverse engineering framework and command-line toolset
https://www.radare.org/
GNU Lesser General Public License v3.0
20.67k stars 3k forks source link

Graph mode can't handle overlapping opcodes in two different functions (6502 arch) #3880

Closed d33tah closed 7 years ago

d33tah commented 8 years ago

Steps to reproduce:

  1. Find a SMB ROM with MD5 811b027eaf99c2def7b933c5208636de,
  2. Run radare -A Super\ Mario\ Bros.\ \(Japan,\ USA\).nes,
  3. Run V command, press right arrow twice, press V,
  4. Observe the call graph

@Maijin said on IRC that it may be because of missing functionality in libr/bin/p/bin_nes.c:

22:30:36  d33tah $ how do i figure out what should be implemented next to move on?
22:30:55  Maijin $ I would go for adding more flags
22:31:03  Maijin $ and check if sections are correct
22:31:06  d33tah $ okay, i see                            
22:31:07  Maijin $ + adding trainers                                               
22:31:25  Maijin $ + adding more info stuff in "iI" like title, and so on

Below is the invalid call graph:


      =--------------------------------------=
      | [0x8002]                             |
      | (fcn) fcn.00008002 62                |
      | ; var int local_0      @ (null)-0x0  |
      | lda #0x10                            |
      | sta 0x2000                           |
      | ldx #0xff                            |
      | txs                                  |
      =--------------------------------------=
          v
        .-'
        |
        | |
    =-------------------------------------------=
    |  0x800a                                   |
    | ; JMP XREF from 0x0000800d (fcn.00008002) |
    | lda 0x2002                                |
    | bpl 0xfb ;[a]                             |
    =-------------------------------------------=
          t f
           .'
           |
 .-------. |
 | =-------------------------------------------=
 | |  0x800f                                   |
 | | ; JMP XREF from 0x00008012 (fcn.00008002) |
 | | lda 0x2002                                |
 | | bpl 0xfb ;[b]                             |
 | =-------------------------------------------=
 `-------' f
           '-----------.
                       |
                       |
               =----------------=
               |  0x8014        |
               | ldy #0xfe      |
               | ldx #0x05      |
               =----------------=
                   v
      .------------'
      |
      |     .-----------------.
  =-------------------------------------------=
  |  0x8018                   |               |
  | ; JMP XREF from 0x00008020 (fcn.00008002) |
  | lda 0x07d7,x              |               |
  | cmp #0x0a                 |               |
  | bcs 0x0c ;[e]             |               |
  =-------------------------------------------=
          f t                 |
          '-------.---------------.
                  |           |   |
                  |           |   |
          =----------------=  |   |
          |  0x801f        |  |   |
          | dex            |  |   |
          | bpl 0xf6 ;[d]  |  |   |
          =----------------=  |   |
                  f `---------'   |
                  |               |
                  |               |
                  |               |
          =----------------=      |
          |  0x8022        |      |
          | lda 0x07ff     |      |
          | cmp #0xa5      |      |
          | bne 0x02 ;[e]  |      |
          =----------------=      |
                  f t             |
            .-----' '-------.     |
            |               |     |
            |               |     |
    =----------------=      |     |
    |  0x8029        |      |     |
    | ldy #0xd6      |      |     |
    =----------------=      |     |
        v                   |     |
      .-'   .---------------'-----'
      |     |
      |     |
  =--------------------------------------------=
  |  0x802b                                    |
  | ; JMP XREF from 0x0000801d (fcn.00008002)  |
  | ; JMP XREF from 0x00008027 (fcn.00008002)  |
  | jsr fcn.000090cc ;[c]                      |
  | sta 0x4011                                 |
  | sta 0x0770                                 |
  | lda #0xa5                                  |
  | sta 0x07ff                                 |
  | sta 0x07a7                                 |
  | lda #0x0f                                  |
  | invalid                                    |
  | invalid                                    |
  =--------------------------------------------=
d33tah commented 8 years ago

@Maijin:

Does that mean that the address for BRK is wrong?

d33tah commented 8 years ago 
13:49:55      zid` $ nothing to do with me why it says invalid instead of STA $4015
13:50:01      zid` $ http://i.imgur.com/mXR7kZa.png

@Maijin: looks like it might be an 6502 issue after all?

d33tah commented 8 years ago

http://nesdev.com/2A03%20technical%20reference.txt

$4015 - DMC/IRQ/length counter status/channel enable register

Does that mean that this address should have a separate R/W region?

d33tah commented 8 years ago

The opcode has a "TODO" message:

=-------------------------------------------------------------------------------------------=
|  0x802b                                                                                   |
| ; JMP XREF from 0x0000801d (fcn.00008002)                                                 |
| ; JMP XREF from 0x00008027 (fcn.00008002)                                                 |
| 0x0000802b 20cc90         1,pc,-,0xff,sp,+,=[2],0x90cc,pc,=,2,sp,-=  ; fcn.000090cc ;[c]  |
| 0x0000802e 8d1140         a,0x4011,=[1]                                                   |
| 0x00008031 8d7007         a,0x0770,=[1]                                                   |
| 0x00008034 a9a5           0xa5,a,=,$z,Z,=,$s,N,=                                          |
| 0x00008036 8dff07         a,0x07ff,=[1]                                                   |
| 0x00008039 8da707         a,0x07a7,=[1]                                                   |
| 0x0000803c a90f           0x0f,a,=,$z,Z,=,$s,N,=                                          |
| 0x0000803e 8d             TODO,invalid                                                    |
| 0x0000803f 15             TODO,invalid                                                    |
=-------------------------------------------------------------------------------------------=
d33tah commented 8 years ago

@Maijin: @XVilka found that this is because the 0x40 byte that sits after 0x8D 0x15 is also a part of a different function and this is not supported yet. Is there already an issue filed for this one?

XVilka commented 8 years ago

This happens because plain Vp mode support those interlapping functions, while graph mode can't. See it in the plain mode:

[0x0000802e 0% 260 smb.nes]> pd $r @ fcn.00008002+44 # 0x802e
│            │   0x0000802e      8d1140         sta 0x4011
│            │   0x00008031      8d7007         sta 0x0770
│            │   0x00008034      a9a5           lda #0xa5
│            │   0x00008036      8dff07         sta 0x07ff
│            │   0x00008039      8da707         sta 0x07a7
│            │   0x0000803c      a90f           lda #0x0f
│            │   0x0000803e  ~   8d1540         sta 0x4015
╒ (fcn) fcn.00008040 1
│            │   ; CALL XREF from 0x0000c490 (fcn.00008040)
╘            │   0x00008040      40             rti
             │   0x00008041      a906           lda #0x06
             │   0x00008043      8d0120         sta 0x2001
             │   0x00008046      202082         jsr fcn.00008220       ;[1]
             │   0x00008049      20198e         jsr fcn.00008e19       ;[2]
d33tah commented 8 years ago

Referencing @ret2libc. Do you think that this would be difficult to fix?

radare commented 8 years ago

The analysis have nothing to do with esil. Esil is just used for emulation and some advanced anlalysis things. Use ao to inspect the low level analysis info of a specific instruction

On 26 Dec 2015, at 17:08, Jacek Wielemborek notifications@github.com wrote:

The opcode has a "TODO" message:

=-------------------------------------------------------------------------------------------= | 0x802b | | ; JMP XREF from 0x0000801d (fcn.00008002) | | ; JMP XREF from 0x00008027 (fcn.00008002) | | 0x0000802b 20cc90 1,pc,-,0xff,sp,+,=[2],0x90cc,pc,=,2,sp,-= ; fcn.000090cc ;[c] | | 0x0000802e 8d1140 a,0x4011,=[1] | | 0x00008031 8d7007 a,0x0770,=[1] | | 0x00008034 a9a5 0xa5,a,=,$z,Z,=,$s,N,= | | 0x00008036 8dff07 a,0x07ff,=[1] | | 0x00008039 8da707 a,0x07a7,=[1] | | 0x0000803c a90f 0x0f,a,=,$z,Z,=,$s,N,= | | 0x0000803e 8d TODO,invalid | | 0x0000803f 15 TODO,invalid | =-------------------------------------------------------------------------------------------= — Reply to this email directly or view it on GitHub.

XVilka commented 8 years ago

It doesn't related to analysis at all, it is a missing feature of the graph mode - see my last comment. On Dec 26, 2015 10:09 PM, "radare" notifications@github.com wrote:

The analysis have nothing to do with esil. Esil is just used for emulation and some advanced anlalysis things. Use ao to inspect the low level analysis info of a specific instruction

On 26 Dec 2015, at 17:08, Jacek Wielemborek notifications@github.com wrote:

The opcode has a "TODO" message:

=-------------------------------------------------------------------------------------------= | 0x802b | | ; JMP XREF from 0x0000801d (fcn.00008002) | | ; JMP XREF from 0x00008027 (fcn.00008002) | | 0x0000802b 20cc90 1,pc,-,0xff,sp,+,=[2],0x90cc,pc,=,2,sp,-= ; fcn.000090cc ;[c] | | 0x0000802e 8d1140 a,0x4011,=[1] | | 0x00008031 8d7007 a,0x0770,=[1] | | 0x00008034 a9a5 0xa5,a,=,$z,Z,=,$s,N,= | | 0x00008036 8dff07 a,0x07ff,=[1] | | 0x00008039 8da707 a,0x07a7,=[1] | | 0x0000803c a90f 0x0f,a,=,$z,Z,=,$s,N,= | | 0x0000803e 8d TODO,invalid | | 0x0000803f 15 TODO,invalid |

=-------------------------------------------------------------------------------------------= — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub https://github.com/radare/radare2/issues/3880#issuecomment-167355071.

radare commented 8 years ago

The graph is generated from the analysis info. So the interleaved function is an artifact of it

On 26 Dec 2015, at 20:23, Anton Kochkov notifications@github.com wrote:

It doesn't related to analysis at all, it is a missing feature of the graph mode - see my last comment. On Dec 26, 2015 10:09 PM, "radare" notifications@github.com wrote:

The analysis have nothing to do with esil. Esil is just used for emulation and some advanced anlalysis things. Use ao to inspect the low level analysis info of a specific instruction

On 26 Dec 2015, at 17:08, Jacek Wielemborek notifications@github.com wrote:

The opcode has a "TODO" message:

=-------------------------------------------------------------------------------------------= | 0x802b | | ; JMP XREF from 0x0000801d (fcn.00008002) | | ; JMP XREF from 0x00008027 (fcn.00008002) | | 0x0000802b 20cc90 1,pc,-,0xff,sp,+,=[2],0x90cc,pc,=,2,sp,-= ; fcn.000090cc ;[c] | | 0x0000802e 8d1140 a,0x4011,=[1] | | 0x00008031 8d7007 a,0x0770,=[1] | | 0x00008034 a9a5 0xa5,a,=,$z,Z,=,$s,N,= | | 0x00008036 8dff07 a,0x07ff,=[1] | | 0x00008039 8da707 a,0x07a7,=[1] | | 0x0000803c a90f 0x0f,a,=,$z,Z,=,$s,N,= | | 0x0000803e 8d TODO,invalid | | 0x0000803f 15 TODO,invalid |

=-------------------------------------------------------------------------------------------= — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub https://github.com/radare/radare2/issues/3880#issuecomment-167355071.

— Reply to this email directly or view it on GitHub.

d33tah commented 8 years ago

W dniu 27.12.2015 o 03:16, radare pisze:

The graph is generated from the analysis info. So the interleaved function is an artifact of it

What are the implications of that? Who could comment on how difficult would it be to fix this issue?

radare commented 8 years ago

Can we have a test script? Just use malloc:// and write+analyze those bytes, it will be easier for testing than carrying around copyrighted material :p

d33tah commented 8 years ago

@radare IIRC @XVilka tried that and failed and I don't know Radare well enough :/

d33tah commented 8 years ago

Ping. What's the status of this bug report?

radare commented 8 years ago

This happens because the analysis is chopping the basic blocks as soon as a new one is happening in the middle.. Maybe one solution would be to check if the split produces invalid instructions and keep both blocks in there.

The function size boundaries is not chopping the basic blocks iirc. Which other situations do you think this can happen to handle it properly?

d33tah commented 8 years ago

@radare: if you're asking me, I unfortunately don't know the problem well enough to speak up. Your proposed solution sounds reasonable to me though. Just curious, does it happen on other architectures as well? Would that be a complex problem to solve?

radare commented 8 years ago

Never seen this issue in other archs/binaries. Thats why i was asking for a sample test

On 10 Jan 2016, at 15:27, Jacek Wielemborek notifications@github.com wrote:

@radare: if you're asking me, I unfortunately don't know the problem well enough to speak up. Your proposed solution sounds reasonable to me though. Just curious, does it happen on other architectures as well? Would that be a complex problem to solve?

— Reply to this email directly or view it on GitHub.

d33tah commented 8 years ago

@radare: did you try to reproduce that on Super Mario Bros?

d33tah commented 8 years ago

@radare: ping

radare commented 8 years ago

Sorry for the late reply. i will have some time to check this issue soon.

d33tah commented 8 years ago

@radare2: ping

radare commented 8 years ago

Sorry i didnt had time to check this issue yet. I willnot fix it for 0.10.1 released this week. But seems an interesting problem to solve for later

On 24 Feb 2016, at 12:59, Jacek Wielemborek notifications@github.com wrote:

@radare2: ping

— Reply to this email directly or view it on GitHub.

d33tah commented 8 years ago

@radare: I see. Is this "later" any specified? ;)

radare commented 8 years ago

hopefully in 1-2 weeks, but as long as my life is kind of a chaos i cant promise anything :D so if anyone else have a chance to take alook it will be great

On 24 Feb 2016, at 19:48, Jacek Wielemborek notifications@github.com wrote:

@radare https://github.com/radare: I see. Is this "later" any specified? ;)

— Reply to this email directly or view it on GitHub https://github.com/radare/radare2/issues/3880#issuecomment-188402213.

d33tah commented 8 years ago

Ping @radare ;)

radare commented 8 years ago

ouch, those two weeks turned to be quite long, this needs rework on the analysis, which is slowly happening, and right now not the main prio for next release. will try to raise the prio a bit

radare commented 7 years ago

this should work with a3a or aab

d33tah commented 7 years ago

If by a3a you meant aaa, it doesn't seem to get it yet:

      .--------------------------------------------------------------.
      | [0x8000] ;[ga]                                               |
      |      ; [0] va=0x00008000 pa=0x00000010 sz=32768 vsz=32768 rw |
      |   ;-- section.ROM:                                           |
      | (fcn) entry0 64                                              |
      |   entry0 (int arg_ffh);                                      |
      | ; arg int arg_ffh @ sp+0xff                                  |
      | sei                                                          |
      | cld                                                          |
      | lda #0x10                                                    |
      | sta sym.PPU_CTRL_REG1                                        |
      | ldx #0xff                                                    |
      | txs                                                          |
      `--------------------------------------------------------------'
          v
          '---------------------------.
                                      |
                                      .
                                      |
                    .-----------------'
                    |
              .-------.
              | .------------------------------------------.
              | |  0x800a ;[gb]                            |
              | |      ; JMP XREF from 0x0000800d (entry0) |
              | | lda sym.PPU_STATUS                       |
              | | bpl 0x00800a ;[gb]                       |
              | `------------------------------------------'
              `-------' f
                        '-------------.
                                      |
                                      .
                                      |
                      .---------------'
                      |
            .-------. |
            | .------------------------------------------.
            | |  0x800f ;[gc]                            |
            | |      ; JMP XREF from 0x00008012 (entry0) |
            | | lda sym.PPU_STATUS                       |
            | | bpl 0x00800f ;[gc]                       |
            | `------------------------------------------'
            `-------' f
                      '--------.
                               |
                               |
                       .--------------------.
                       |  0x8014 ;[gd]      |
                       | ldy #0xfe          |
                       | ldx #0x05          |
                       `--------------------'
                           v
                .----------'
                |
                |     .--------------------.
            .------------------------------------------.
            |  0x8018 ;[gf]                |           |
            |      ; JMP XREF from 0x00008020 (entry0) |
            | lda 0x07d7,x                 |           |
            | cmp #0x0a                    |           |
            | bcs 0x00802b ;[ge]           |           |
            `------------------------------------------'
                    f t                    |
                    '-----.----------------|--.
                          |                |  |
                          |                |  |
                  .---------------------.  |  |
                  |  0x801f ;[gg]       |  |  |
                  | dex                 |  |  |
                  | bpl 0x008018 ;[gf]  |  |  |
                  `---------------------'  |  |
                          f `--------------'  |
                          |                   |
                          |                   |
                          |                   |
                  .---------------------.     |
                  |  0x8022 ;[gh]       |     |
                  | lda 0x07ff          |     |
                  | cmp #0xa5           |     |
                  | bne 0x00802b ;[ge]  |     |
                  `---------------------'     |
                          f t                 |
                    .-----' '-----------.     |
                    |                   |     |
                    |                   |     |
            .--------------------.      |     |
            |  0x8029 ;[gi]      |      |     |
            | ldy #0xd6          |      |     |
            `--------------------'      |     |
                v                       |     |
                '-.     .---------------'-----'
                  |     |
                  |     |
              .-------------------------------------------.
              |  0x802b ;[ge]                             |
              |      ; JMP XREF from 0x0000801d (entry0)  |
              |      ; JMP XREF from 0x00008027 (entry0)  |
              | jsr fcn.000090cc ;[gj]                    |
              | sta 0x4011                                |
              | sta 0x0770                                |
              | lda #0xa5                                 |
              | sta 0x07ff                                |
              | sta 0x07a7                                |
              | lda #0x0f                                 |
              | invalid                                   |
              | invalid                                   |
              `-------------------------------------------'

Tested on Super Mario Bros (E).nes found on https://www.loveroms.com/ (MD5: 673913a23cd612daf5ad32d4085e0760)

Maijin commented 7 years ago

No r2pm -i a3a, but I don't see point of installing extra analysis, this should be done by core. @radare

radare commented 7 years ago

Yes i know but aab will do that. And it requires lot of testing and rethinking of the current model. Just informing that its not yet ready but experimenting on new things may help solving it quickier

On 10 Mar 2017, at 19:59, Maijin notifications@github.com wrote:

No r2pm -i a3a, but I don't see point of installing extra analysis, this should be done by core. @radare

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

radare commented 7 years ago

can you try with aab?

radare commented 7 years ago

HELLO ANYONE THERE

Maijin commented 7 years ago

The output is now completly different, someone knowing 6502 would need to check again, i'm closing until someone follow-up

radare commented 7 years ago

this is unrelated to the graph rendering. but imho this thing should work fine with aab.

On 12 Sep 2017, at 17:34, Maijin notifications@github.com wrote:

The output is now completly different, someone knowing 6502 would need to check again, i'm closing until someone follow-up

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/radare/radare2/issues/3880#issuecomment-328870881, or mute the thread https://github.com/notifications/unsubscribe-auth/AA3-lkTQjXbXvve_1fSgWwnLKfr81erTks5shpWCgaJpZM4G7Xxx.