Kesalahan Statistik

http://www.cs.cornell.edu/~asampson/blog/statsmistakes.html

Computer scientists in systemsy fields, myself included, aren’t great at using statistics. Maybe it’s because there are so many other potential problems with empirical evaluations that solid statistical reasoning doesn’t seem that important. Other subfields, like HCI and machine learning, have much higher standards for data analysis. Let’s learn from their example.
Here are three kinds of avoidable statistics mistakes that I notice in published papers.

No Statistics at All

The most common blunder is not using statistics at all when your paper clearly uses statistical data. If your paper uses the phrase “we report the average time over 20 runs of the algorithm,” for example, you should probably use statistics.
Here are two easy things that every paper should do when it deals with performance data or anything else that can randomly vary:
First, plot the error bars. In every figure that represents an average, compute the standard error of the mean or just the plain old standard deviation and add little whiskers to each bar. Explain what the error bars mean in the caption.

Second, do a simple statistical test. If you ever say “our system’s average running time is X seconds, which is less than the baseline running time of Y seconds,” you need show that the difference is statistically significant. Statistical significance tells the reader that the difference you found was more than just “in the noise.”
For most CS papers I read, a really basic test will work: Student’s $t$t-test checks that two averages that look different actually are different. The process is easy. Collect some $N$N samples from the two conditions, compute the mean $\overline{X}$​X​​​ and the standard deviation $s$s for each, and plug them into this formula:
$t = \frac{ \overline{X}_1 - \overline{X}_2 } { \sqrt{ \frac{s_1^2}{N_1} + \frac{s_2^2}{N_2} } }$t=​√​​N​1​​​​s​1​2​​​​+​N​2​​​​s​2​2​​​​​​​​​​X​​​​1​​−​X​​​​2​​​​
then plug that $t$t into the cumulative distribution function of the $t$t-distribution to get a $p$p-value. If your $p$p-value is below a threshold $\alpha$α that you chose ahead of time (0.05 or 0.01, say), then you have a statistically significant difference. Your favorite numerical library probably already has an implementation that does all the work for you.
If you’ve taken even an intro stats course, you know all this already! But you might be surprised to learn how many computer scientists don’t. Program committees don’t require that papers use solid statistics, so the literature is full of statistics-free but otherwise-good papers, so standards remain low, and Prof. Ouroboros keeps drawing figures without error bars. Other fields are moving beyond the $p$p-value, and CS isn’t even there yet.

Failure to Reject = Confirmation

When you do use a statistical test in a paper, you need to interpret its results correctly. When your test produces a $p$p-value, here are the correct interpretations:

• If $p < \alpha$p<α: The difference between our average running time and the baseline’s average running time is statistically significant. Pedantically, we reject the null hypothesis that says that the averages might be the same.
• Otherwise, if $p \ge \alpha$p≥α: We conclude nothing at all. Pedantically, we fail to reject that null hypothesis.

It’s tempting to think, when $p \ge \alpha$p≥α, that you’ve found the opposite thing from the $p < \alpha$p<α case: that you get to conclude that there is no statistically significant difference between the two averages. Don’t do that!
Simple statistical tests like the $t$t-test only tell you when averages are different; they can’t tell you when they’re the same. When they fail to find a difference, there are two possible explanations: either there is no difference or you haven’t collected enough data yet. So when a test fails, it could be your fault: if you had run a slightly larger experiment with a slightly larger $N$N, the test might have successfully found the difference. It’s always wrong to conclude that the difference does not exist.
If you want to claim that two means are equal, you’ll need to use a different test where the null hypothesis says that they differ by at least a certain amount. For example, an appropriate one-tailed $t$t-test will do.

The Multiple Comparisons Problem

In most ordinary evaluation sections, it’s probably enough to use only a handful of statistical tests to draw one or two bottom-line conclusions. But you might find yourself automatically running an unbounded number of comparisons. Perhaps you have $n$n benchmarks, and you want to compare the running time on each one to a corresponding baseline with a separate statistical test. Or maybe your system works in a feedback loop: it tries one strategy, performs a statistical test to check whether the strategy worked, and starts over with a new strategy otherwise.
Repeated statistical tests can get you into trouble. The problem is that every statistical test has a probability of lying to you. The probability that any single test is wrong is small, but if you do lots of test, the probability amplifies quickly.
For example, say you choose $\alpha = 0.05$α=0.05 and run one $t$t-test. When the test succeeds—when it finds a significant difference—it’s telling you that there’s at most an $\alpha$α chance that the difference arose from random chance. In 95 out of 100 parallel universes, your paper found a difference that actually exists. I’d take that bet.
Now, say you run a series of $n$n tests in the scope of one paper. Then every test has an $\alpha$α chance of going wrong. The chances that your paper has more than $k$k errors in it is given by the binomial distribution:
$1 - \sum_{i=0}^{k} {n \choose i} \alpha^i (1-\alpha)^{n-i}$1−​i=0​∑​k​​(​i​n​​)α​i​​(1−α)​n−i​​
which grows exponentially with the number of tests, $n$n. If you use just 10 tests with $\alpha = 0.05$α=0.05, for example, your chance of having one test go wrong grows to 40%. If you do 100, the probability is above 99%. At that point, it’s a near certainty that your paper is misreporting some result.
(To compute these probabilities yourself, set $k = 0$k=0 so you get the chance of at least one error. Then the CDF above simplifies down to $1 - (1 - \alpha) ^ n$1−(1−α)​n​​.)
This pitfall is called the multiple comparisons problem. If you really need to run lots of tests, all is not lost: there are standard ways to compensate for the increased chance of error. The simplest is the Bonferroni correction, where you reduce your per-test $\alpha$α to $\frac{\alpha}{n}$​n​​α​​ to preserve an overall $\alpha$α chance of going wrong.

Using Drupal's autocomplete on a custom form element

http://www.jochenhebbrecht.be/site/2011-01-10/drupal/using-drupals-autocomplete-a-custom-form-element

Did you ever created a custom form? A place where you couldn't use the Form API of Drupal?
Imagine this form, and you want to create an autocomplete feature on the nickname. The moment you start typing a nickname, a list of usernames get in the textfield.

<form action="/foo">
   ...
   <input type="text" value="Nickname"></input>
   <input type="submit" value="Submit"></input>
</form>

Step 1: adjust the HTML code

• Start from a normal text field

<input id="txt-existing-bidder" type="text"></input>

• Add attributes to normal text field

<input id="txt-nickname" type="text" class="form-text form-autocomplete text"
       autocomplete="OFF"></input>

• Add a hidden value to capture the autocomplete values. Put this field immediately after the textfield

<input class="autocomplete" type="hidden" id="txt-nickname-autocomplete"
       value="/##path_to_autocomplete##"/autocomplete" disabled="disabled" />

Step 2: adjust the Javascript code

• You need the following JS files to have a fully working version:
  

  drupal_add_js("misc/autocomplete.js");
  drupal_add_js("misc/ahah.js");

• If the HTML (see above) is added by AJAX, Drupal's autocomplete will not discover the autocomplete fields. Therefore, execute following code after loading the AJAX call
  

  Drupal.attachBehaviors($("##CONTEXT##"));

  
  ##CONTEXT##: reference to a div which hold the input

Step 3: create a autocomplete PHP function which returns a JSON object

/**
 * Searches all auction users and returns a JSON object of all users
 * @param $search the value to be searched
 * @return JSON object with all users
 */
function autocomplete_users($search = '') {
        // TODO: implement search function here
 
        // DEBUG
 $users['admin {uid:1}'] = 'admin';
 $users['jochen {uid:2}'] = 'jochen';
 
 return drupal_json($users);
}

Step 4: the result

http://kazlauskas.me/entries/x64-uefi-os-1.html

• Index
• Contact
• About

A x64 OS #1: UEFI

2016-03-03 (Updated: 2016-03-04)

As a part of the OS pro­ject for the uni­ver­sity there has been a re­quest to also write up the ex­per­i­ences and chal­lenges en­countered. This is the first post of the series on writ­ing a x64 op­er­at­ing sys­tem when boot­ing straight from UE­FI. Please keep in mind that these posts are writ­ten by a not-even-hob­by­ist and con­tent in these posts should be taken with a grain of salt.

Ker­nel and UEFI

I’ve de­cided to write a ker­nel tar­get­ing x64 as a UEFI ap­plic­a­tion. There is a num­ber of ap­peals to write a ker­nel as UEFI ap­plic­a­tion as op­posed to writ­ing a multi­boot ker­nel. Namely:

1. For x86 fam­ily of pro­cessors, you avoid the work ne­ces­sary to up­grade from real mode to pro­tec­ted mode and then from pro­tec­ted mode to long mode which is more com­monly known as 64-bit mode. As a UEFI ap­plic­a­tion your ker­nel gets a fully work­ing x64 en­vir­on­ment from a get-go;
2. Un­like BIOS, UEFI is a well doc­u­mented firm­ware. Most of the in­ter­faces provided by BIOS are de facto and you’re lucky if they work at all, while most of these provided by UEFI are de jure and usu­ally just work;
3. UEFI is ex­tens­ible, whereas BIOS is not really;
4. Fi­nally, UEFI is the mod­ern tech­no­logy which is to stay around, while BIOS is a 40 years old piece of tech­no­logy on death row. Learn­ing about soon-to-be-dead tech­no­logy is waste of the ef­fort.

Des­pite my strong at­tach­ment to the Rust com­munity and Rust’s per­fect suit­ab­il­ity for ker­nels¹, I’ll be writ­ing the ker­nel in C. Mostly be­cause it is un­likely people in­side the uni­ver­sity will be fa­mil­iar with Rust, but also be­cause GNU-EFI is a C lib­rary and I can­not be bothered to bind it. I’d surely be writ­ing it in Rust were I more ser­i­ous about the pro­ject.

Tool­chain

As it turns out, de­vel­op­ing a x64 ker­nel on a x64 host greatly sim­pli­fies set­ting up the build tool-­chain. I’ll be us­ing:

• clang to com­pile the C code (no cross-­com­piler is ne­ces­sary²!);
• gnu-efi lib­rary to in­ter­act with the UEFI firm­ware;
• qemu emu­lator to run my ker­nel; and
• OVMF as the UEFI firm­ware.

The UEFI “Hel­lo, world!”

The fol­low­ing snip­pet of code is all the code you need to print some­thing on the screen as an UEFI ap­plic­a­tion:

// main.c
#include <efi.h>
#include <efilib.h>
#include <efiprot.h>

EFI_STATUS
efi_main (EFI_HANDLE ImageHandle, EFI_SYSTEM_TABLE *SystemTable)
{
    InitializeLib(ImageHandle, SystemTable);
    Print(L"Hello, world from x64!");
    for(;;) __asm__("hlt");
}

However, com­pil­ing this code cor­rectly is not as trivi­al. Fol­low­ing three com­mands are ne­ces­sary to pro­duce a work­ing UEFI ap­plic­a­tion:

clang -I/usr/include/efi -I/usr/include/efi/x86_64 -I/usr/include/efi/protocol -fno-stack-protector -fpic -fshort-wchar -mno-red-zone -DHAVE_USE_MS_ABI -c -o src/main.o src/main.c
ld -nostdlib -znocombreloc -T /usr/lib/elf_x86_64_efi.lds -shared -Bsymbolic -L /usr/lib /usr/lib/crt0-efi-x86_64.o src/main.o -o huehuehuehuehue.so -lefi -lgnuefi
objcopy -j .text -j .sdata -j .data -j .dynamic -j .dynsym  -j .rel -j .rela -j .reloc --target=efi-app-x86_64 huehuehuehuehue.so huehuehuehuehue.efi

The clang com­mand is pretty self-­ex­plan­at­ory: we tell the com­piler where to look for the EFI head­ers and what to com­pile into a ob­ject file. Prob­ably the most non-trivial op­tion here is the -DHAVE_USE_MS_ABI one – x64 UEFI uses the Win­dows’ x64 call­ing con­ven­tion, and not the reg­u­lar C one, thus all ar­gu­ments in calls to UEFI func­tions must be passed in a dif­fer­ent way than it is usu­ally done in C code. His­tor­ic­ally this con­ver­sion was done by the uefi_call_wrapper wrap­per, but clang sup­ports the call­ing con­ven­tion nat­ively, and we tell that fact to the gnu-efi lib­rary with this op­tion³.
Then, I manu­ally link my ob­ject file and UE­FI-spe­cific C runtime up into a shared lib­rary us­ing a cus­tom linker script provided by the gnu-efi lib­rary. The res­ult is an ELF lib­rary about 250KB in size. However, UEFI ex­pects its ap­plic­a­tions in PE ex­ecut­able form­at, so we must con­vert our lib­rary into the de­sired format with the objcopy com­mand. At this point huehuehuehuehue.efi file should be pro­duced and ma­jor­ity of UEFI firm­wares should be able to run it.
In prac­tice, I’ve auto­mated these steps along with a con­sid­er­ably com­plex se­quence of build­ing im­age files I’ve stolen from OS­DEV’s tu­torial on cre­at­ing im­ages into a Make­file. Feel free to copy it in parts or in whole for your own use cases.

UEFI boot and runtime ser­vices

A UEFI ap­plic­a­tion has 2 dis­tinct stages over its life­time: a stage where so-c­alled boot ser­vices are avail­able and stage after these boot ser­vices are dis­abled. An UEFI ap­plic­a­tion will be launched by the UEFI firm­ware and both boot and runtime ser­vices will be avail­able to the ap­plic­a­tion. Most not­ably, boot ser­vices provide APIs for load­ing other UEFI ap­plic­a­tions (e.g. im­ple­ment­ing boot­load­er­s), hand­ling (al­loc­at­ing and deal­loc­at­ing) memory and us­ing pro­to­cols (speak­ing to other act­ive UEFI ap­plic­a­tion­s).
Once the ker­nel is done with us­ing boot ser­vices it calls ExitBootServices which is a method provided by… a boot ser­vice. Past that point only runtime ser­vices are avail­able and you can­not ever re­turn to a state where boot ser­vices are avail­able ex­cept by re­set­ting the sys­tem. Man­aging UEFI vari­ables, sys­tem clock and re­set­ting the sys­tem is pretty much the only things you can do with the runtime ser­vices.
For my ker­nel, I will use the graph­ics out­put pro­tocol to set up the video frame buf­fer, exit the boot ser­vices and, fi­nally, shut down the ma­chine be­fore reach­ing the hlt in­struc­tion. Fol­low­ing piece of code im­ple­ments the de­scribed se­quence. I left some code out, you can see it in full at Git­lab. For ex­ample, the defin­i­tion of init_graphics.

EFI_STATUS
efi_main (EFI_HANDLE ImageHandle, EFI_SYSTEM_TABLE *SystemTable)
{
    EFI_STATUS status;
    InitializeLib(ImageHandle, SystemTable);

    // Initialize graphics
    EFI_GRAPHICS_OUTPUT_PROTOCOL *graphics;
    EFI_GUID graphics_proto = EFI_GRAPHICS_OUTPUT_PROTOCOL_GUID;
    status = SystemTable->BootServices->LocateProtocol(&graphics_proto, NULL, (void **)&graphics);
    if(status != EFI_SUCCESS) return status;
    status = init_graphics(graphics);
    if(status != EFI_SUCCESS) return status;

    // Figure out the memory map (should be identity mapping)
    boot_state.memory_map = LibMemoryMap(&boot_state.memory_map_size,
                                         &boot_state.map_key,
                                         &boot_state.descriptor_size,
                                         &boot_state.descriptor_version);
    // Exit the boot services...
    SystemTable->BootServices->ExitBootServices(ImageHandle, boot_state.map_key);
    // and set up the memory map we just found.
    SystemTable->RuntimeServices->SetVirtualAddressMap(boot_state.memory_map_size,
                                                       boot_state.descriptor_size,
                                                       boot_state.descriptor_version,
                                                       boot_state.memory_map);
    // Once we’re done we power off the machine.
    SystemTable->RuntimeServices->ResetSystem(EfiResetShutdown, EFI_SUCCESS, 0, NULL);
    for(;;) __asm__("hlt");
}

Note, that some pro­to­cols can either be at­tached to your own EFI_HANDLE or some other EFI_HANDLE (i.e. pro­tocol is provided by an­other UEFI ap­plic­a­tion). Graph­ics out­put pro­tocol I’m us­ing here is an ex­ample of a pro­tocol at­tached to an­other EFI_HANDLE, there­fore we use LocateProtocol boot ser­vice to find it. In the off-chance the pro­tocol is at­tached to ap­plic­a­tion’s own EFI_HANDLE, the HandleProtocol method should be used in­stead:

EFI_LOADED_IMAGE *loaded_image = NULL;
EFI_GUID loaded_image_protocol = LOADED_IMAGE_PROTOCOL;
EFI_STATUS status = SystemTable->BootServices->HandleProtocol(ImageHandle, &loaded_image_protocol, &loaded_image);

Next steps

At this point I have a bare bones frame for my awe­some ker­nel called “hue­hue­hue­hue­hue”. From this point on­wards the de­vel­op­ment of the ker­nel should not dif­fer much from the tra­di­tional de­vel­op­ment of any other x64 ker­nel. Next, I’ll be im­ple­ment­ing soft­ware and hard­ware in­ter­rupts; ex­pect a post on that.

Footnotes

1. As proved by nu­mer­ous ker­nels writ­ten in Rust out there.↩
2. That be­ing said, clang can cross-­com­pile without hav­ing to build it from source for that pur­pose in the first place, like it is ne­ces­sary to do with gcc.↩
3. If gnu-efi was a per­fect lib­rary, the -DGNU_EFI_USE_MS_ABI op­tion should be used in­stead, but the lib­rary only ver­sion-checks for gcc and al­ways re­ports that clang does not sup­port the op­tion.↩

Hakyll

CC BY 3.0

"Reverse Engineering for Beginners" free book

"Reverse Engineering for Beginners" free book

http://beginners.re/

Reverse Engineering challenges

Contrived by Dennis Yurichev (yurichev.com).
The website has been inspired by Project Euler and "the matasano crypto challenges".
http://challenges.re/#Solutions

The Matasano Crypto Challenges

https://blog.pinboard.in/2013/04/the_matasano_crypto_challenges/

Android: Collecting and Plotting Accelerometer Data

Android: Collecting and Plotting Accelerometer Data 

https://androidstream.wordpress.com/2013/01/16/android-collecting-and-plotting-accelerometer-data/

Loggin accelerometer from Android to PC
http://simena86.github.io/blog/2013/04/30/logging-accelerometer-from-android-to-pc/

High frequency security bug hunting: 120 days, 120 bugs

https://shubs.io/high-frequency-security-bug-hunting-120-days-120-bugs/