Recherche avancée

Sur d’autres sites (11263)

• Fighting with the VP8 Spec

  4 juin 2010, par Multimedia Mike — VP8

  As stated in a previous blog post on the matter, FFmpeg’s policy is to reimplement codecs rather than adopt other codebases wholesale. And so it is with Google’s recently open sourced VP8 codec, the video portion of their Webm initiative. I happen to know that the new FFmpeg implementation is in the capable hands of several of my co-developers so I’m not even worrying about that angle.

  Instead, I thought of another of my characteristically useless exercises : Create an independent VP8 decoder implementation entirely in pure Python. Silly ? Perhaps. But it has one very practical application : By attempting to write a new decoder based on the official bitstream documentation, this could serve as a mechanism for validating said spec, something near and dear to my heart.

  What is the current state of the spec ? Let me reiterate that I’m glad it exists. As I stated during the initial open sourcing event, everything that Google produced for the initial event went well beyond my wildest expectations. Having said that, the documentation does fall short in a number of places. Fortunately, I am on the Webm mailing lists and am sending in corrections and ideas for general improvement. For the most part, I have been able to understand the general ideas behind the decoding flow based on the spec and am even able to implement certain pieces correctly. Then I usually instrument the libvpx source code with output statements in order to validate that I’m doing everything right.

  Token Blocker
  Unfortunately, I’m quite blocked right now on the chapter regarding token/DCT coefficient decoding (chapter 13 in the current document iteration). In his seminal critique of the codec, Dark Shikari complained that large segments of the spec are just C code fragments copy and pasted from the official production decoder. As annoying as that is, the biggest insult comes at the end of section 13.3 :

  While we have in fact completely described the coefficient decoding procedure, the reader will probably find it helpful to consult the reference implementation, which can be found in the file detokenize.c.

  The reader most certainly will not find it helpful to consult the file detokenize.c. The file in question implements the coefficient residual decoding with an unholy sequence of C macros that contain goto statements. Honestly, I thought I did understand the coefficient decoding procedure based on the spec’s description. But my numbers don’t match up with the official decoder. Instrumenting or tracing macro’d code is obviously painful and studying the same code is making me think I don’t understand the procedure after all. To be fair, entropy decoding often occupies a lot of CPU time for many video decoders and I have little doubt that the macro/goto approach is much faster than clearer, more readable methods. It’s just highly inappropriate to refer to it for pedagogical purposes.

  Aside : For comparison, check out the reference implementation for the VC-1 codec. It was written so clearly and naively that the implementors used an O(n) Huffman decoder. That’s commitment to clarity.

  I wonder if my FFmpeg cohorts are having better luck with the DCT residue decoding in their new libavcodec implementation ? Maybe if I can get this Python decoder working, it can serve as a more appropriate reference decoder.

  Update : Almost immediately after I posted this entry, I figured out a big problem that was holding me back, and then several more small ones, and finally decoded by first correct DCT coefficient from the stream (I’ve never been so happy to see the number -448). I might be back on track now. Even better was realizing that my original understanding of the spec was correct.

  Unrelated
  I found this image on the Doom9 forums. I ROFL’d :
  

  
  
  

  It’s probably unfair and inaccurate but you have to admit it’s funny. Luckily, quality nitpickings aren’t my department. I’m just interested in getting codecs working, tested, and documented so that more people can use them reliably.

• WebVTT explained

  5 avril 2011, par silvia

  On Wednesday, I gave a talk at Google about WebVTT, the Web Video Text Track file format that is under development at the WHATWG for solving time-aligned text challenges for video. I started by explaining all the features that WebVTT supports for captions and subtitles, mentioned how WebVTT (...)

• Heroic Defender of the Stack

  27 janvier 2011, par Multimedia Mike — Programming

  Problem Statement

  I have been investigating stack smashing and countermeasures (stack smashing prevention, or SSP). Briefly, stack smashing occurs when a function allocates a static array on the stack and writes past the end of it, onto other local variables and eventually onto other function stack frames. When it comes time to return from the function, the return address has been corrupted and the program ends up some place it really shouldn’t. In the best case, the program just crashes ; in the worst case, a malicious party crafts code to exploit this malfunction.

  Further, debugging such a problem is especially obnoxious because by the time the program has crashed, it has already trashed any record (on the stack) of how it got into the errant state.

  Preventative Countermeasure

  GCC has had SSP since version 4.1. The computer inserts SSP as additional code when the -fstack-protector command line switch is specified. Implementation-wise, SSP basically inserts a special value (the literature refers to this as the ’canary’ as in "canary in the coalmine") at the top of the stack frame when entering the function, and code before leaving the function to make sure the canary didn’t get stepped on. If something happens to the canary, the program is immediately aborted with a message to stderr about what happened. Further, gcc’s man page on my Ubuntu machine proudly trumpets that this functionality is enabled per default ever since Ubuntu 6.10.

  And that’s really all there is to it. Your code is safe from stack smashing by default. Or so the hand-wavy documentation would have you believe.

  Not exactly

  Exercising the SSP

  I wanted to see the SSP in action to make sure it was a real thing. So I wrote some code that smashes the stack in pretty brazen ways so that I could reasonably expect to trigger the SSP (see later in this post for the code). Here’s what I learned that wasn’t in any documentation :

  SSP is only emitted for functions that have static arrays of 8-bit data (i.e., [unsigned] chars). If you have static arrays of other data types (like, say, 32-bit ints), those are still fair game for stack smashing.

  Evaluating the security vs. speed/code size trade-offs, it makes sense that the compiler wouldn’t apply this protection everywhere (I can only muse about how my optimization-obsessive multimedia hacking colleagues would absolute freak out if this code were unilaterally added to all functions). So why are only static char arrays deemed to be "vulnerable objects" (the wording that the gcc man page uses) ? A security hacking colleague suggested that this is probably due to the fact that the kind of data which poses the highest risk is arrays of 8-bit input data from, e.g., network sources.

  The gcc man page also lists an option -fstack-protector-all that is supposed to protect all functions. The man page’s definition of "all functions" perhaps differs from my own since invoking the option does not have differ in result from plain, vanilla -fstack-protector.

  The Valgrind Connection

  "Memory trouble ? Run Valgrind !" That may as well be Valgrind’s marketing slogan. Indeed, it’s the go-to utility for finding troublesome memory-related problems and has saved me on a number of occasions. However, it must be noted that it is useless for debugging this type of problem. If you understand how Valgrind works, this makes perfect sense. Valgrind operates by watching all memory accesses and ensuring that the program is only accessing memory to which it has privileges. In the stack smashing scenario, the program is fully allowed to write to that stack space ; after all, the program recently, legitimately pushed that return value onto the stack when calling the errant, stack smashing function.

  Valgrind embodies a suite of tools. My idea for an addition to this suite would be a mechanism which tracks return values every time a call instruction is encountered. The tool could track the return values in a separate stack data structure, though this might have some thorny consequences for some more unusual program flows. Instead, it might track them in some kind of hash/dictionary data structure and warn the programmer whenever a ’ret’ instruction is returning to an address that isn’t in the dictionary.

  Simple Stack Smashing Code

  Here’s the code I wrote to test exactly how SSP gets invoked in gcc. Compile with ’gcc -g -O0 -Wall -fstack-protector-all -Wstack-protector stack-fun.c -o stack-fun’.

  stack-fun.c :

  PLAIN TEXT

  C :

  1. /* keep outside of the stack frame */
  2. static int i ;
  3.  
  4. void stack_smasher32(void)
  5. {
  6.  int buffer32[8] ;
  7.  // uncomment this array and compile without optimizations
  8.  // in order to force this function to compile with SSP
  9. // char buffer_to_trigger_ssp[8] ;
  10.  
  11.  for (i = 0 ; i <50 ; i++)
  12.   buffer32[i] = 0xA5 ;
  13. }
  14.  
  15. void stack_smasher8(void)
  16. {
  17.  char buffer8[8] ;
  18.  for (i = 0 ; i <50 ; i++)
  19.   buffer8[i] = 0xA5 ;
  20. }
  21.  
  22. int main()
  23. {
  24. // stack_smasher8() ;
  25.  stack_smasher32() ;
  26.  return 0 ;
  27. }

  The above incarnation should just produce the traditional "Segmentation fault". However, uncommenting and executing stack_smasher8() in favor of stack_smasher32() should result in "*** stack smashing detected *** : ./stack-fun terminated", followed by the venerable "Segmentation fault".

  As indicated in the comments for stack_smasher32(), it’s possible to trick the compiler into emitting SSP for a function by inserting an array of at least 8 bytes (any less and SSP won’t emit, as documented, unless gcc’s ssp-buffer-size parameter is tweaked). This has to be compiled with no optimization at all (-O0) or else the compiler will (quite justifiably) optimize away the unused buffer and omit SSP.

  For reference, I ran my tests on Ubuntu 10.04.1 with gcc 4.4.3 compiling the code for both x86_32 and x86_64.