Computer things

A brief intro to Answer Set Programming (ASP).

Warning: this is a rather isolated, conceptual point of view*.

If I were to create myself a robot slave, after dealing with all the perception and movement issues, I would want to give him some sort of brain. Now I don’t want a dumb robot – he needs to be able to have a (limited) understanding of the world around him and be able to reason about things so I don’t have to explain every little thing to him. However, if he tried to do something that I do not like, such as putting my cat in the microwave, I would like to be able to understand his ‘thoughts’ and ‘beliefs’ about the world so I could address this.

ASP is a logic based, non-monotonic language used to represent knowledge about the world and reason with it. A program has some facts, relations and rules about things (human readable! not just a bunch of numbers!). When given a goal or some facts and passed through a solver it can logically reason how to achieve that goal or how that fact occurred. As ASP is declarative, an ASP program does not need to be told how to accomplish its goal – given enough information about the world an ASP solver can work it out.

What do you mean by ‘declarative’?

If you’ve done programming before it was probably ‘imperative’ programming, where you tell the computer exactly how to do things and it does them. That is not how this works. Instead we give the computer a bunch of rules and constraints about its environment, a current state and a final state and the solver works out all the possible logical ways to get from the current state to the final state based off the rules and constraints.

And ‘non-monotonic’?

In this context this means that given new information we can retract previous beliefs. If the computer generated an explanation for a coffee cup appearing on my desk, it may come up with the belief that I put it there. If it were then told that Bob was using my desk today, it could form the new belief that Bob put the coffee cup there, not me.

Okay, so how do I write ASP?

A program consists of atoms, literals and rules. An atom ‘a’ is the smallest proposition in the program and can be true or false ( a false atom is prepended with a ‘-‘. Literals are either a or not a – where ‘not a’ means that we have no reason to believe that a is true).

For example, given the atom ‘light_on(hallway)’ I have four possible literals/beliefs:

  1.  The hallway light is on: ‘light_on(hallway)’.
  2.  The hallway light is not on (aka it is off): ‘-light_on(hallway)’.
  3.  It is not known if the hallway light is on: ‘not light_on(hallway)’.
  4.  It is not known if the hallway light is off: ‘not -light_on(hallway)’.

A rule is of the form ‘head ← body.’. If the body (one or more beliefs) is true then we can infer the head (a single belief) to be true. A rule with just the head, ‘head ←.’ , is called a fact and must always be true. Similarly, a rule with just the body ‘← body.’ must never be true.

Solving an ASP program generates an ‘answer set’ which is a collection of all the beliefs that we know and can infer – ie all the beliefs that satisfy all the rules of the program.

Using these (and glossing over a few other things we need to define) we can construct rules such as:

  • if the hallway light is on then the robot should turn it off: ‘robot(turn_off(hallway), time) :- light_on(hallway).’
  • if a person picks up an object that was on a table, the object is now in the person’s hand and not where it used to be: ‘location(object, person, time2) :- picks_up(person, object, time1), location(object, table, time1).’

The ability to be able to have unknown beliefs combined with non-monoticity allows us to reason with incomplete knowledge and have default assumptions:

  • an object will generally remain where it is: ‘location(object, place1, time+1) :- location(object, place1 time), not location(object, P, time+1), place(P).’

(If we know an object is at place1 at a give time – location(object, place1 time) – and that we do not have information where the object is at the next instant in time – not location(object, P, time+1), place(P) – then we can believe that the object stays at the same place – location(object, place1, time+1).)

  • most books belong in the study: ‘belongs_in(book1, study) :- not -belongs_in(book1, study).’

If we haven’t been told that this particular book doesn’t belong in the study – ‘ not -belongs_in(book1, study)’ – then assume that it does belong there – ‘belongs_in(book1, study)‘. If later on the robot gets some information that a cookbook belongs in the kitchen, it will use a combination of beliefs and rules:

  1. all cookbooks belong in the kitchen
  2. this book is a cookbook
  3. an object can only be in one place, so it cannot be in the study

As you may be able to infer from the above example, the solver looks for beliefs that do not invalidate any constraints and as such our constraints/rules need to be thought about carefully – using a formal structure helps a lot with this.

Action Language

No one is forcing you to write ASP such that it follows an action language, just as no one is stopping you from writing your own assembly language. However, it is what the convention is and some tools being developed will assume you have written your program in this way. Also, breaking down the rules, properties and relations of the environment into this formal structure helps with debugging, and breaking down the program into smaller chunks for automation/scripts (in my work with ASP we used reinforcement learning to learning new executability conditions, meaning they could easily be added into the existing knowledge base automatically.).

  • Causal laws: executing an action a in a given state defined by properties p 0 , …, p m causes the inertial fluent f in to be true. For example ‘If a robot puts down an object it
    no longer has the object’: putdown(R, O, L) causes − has object(R, O).
  • State constraints: a state defined by p 0 , …, p m also satisfies property f . For example ‘an entity cannot be above itself’: −above(E1, E2) if E1 = E2.
  • Executability conditions: its impossible for actions a 0 , …, a n to occur in the state defined by properties p 0 , …, p m . For example ‘a robot can only hold one object
    at a time’: impossible pickup(R, O1) if has object(R, O2), O1 ! = O2.

 

Logic programming languages aren’t known for their computational speed, and ASP is no exception. Typical solvers generate a complete answer set – i.e a belief for absolutely everything it knows about for all time steps – which grow insanely quickly. In terms of most uses this is not required and not wanted (as it slows things down massively) – I do believe partial solvers have/are being developed so we only need to reason about a particular subset of things.

* If you want the formal stuff, go read a textbook. I only spent a year dabbling with ASP in my third year of Engineering for a particular application (with no prior experience in formal logic, prologs, computer science etc) and this was almost a year ago – so take everything with a grain handful of salt.

 

Standard
Kernel, Linux, Uncategorized

SROP Mitigation

 

What is SROP???

Sigreturn Oriented Programming – a general technique that can be used as an exploit, or as a backdoor to exploit another vulnerability.

Okay, but what is it??

Yeah… Let me take you through some relevant background info, where I skimp on the details and give you the general picture.

In Linux, software interrupts are called signals. More about signals here! Generally a signal will convey some information from the kernel and so most signals will have a specific signal handler (some code that deals with the signal) setup.

Signals are asynchronous – ie they can be sent to a process/program at anytime. When a signal arrives for a process, the kernel suspends the process. The kernel then saves the ‘context’ of the process – all the general purpose registers (GPRs), the stack pointer, the next-instruction pointer etc – into a structure called a ‘sigframe’. The sigframe is stored on the stack, and then the kernel runs the signal handler. At the very end of the signal handler, it calls a special system call called ‘sigreturn’ – indicating to the kernel that the signal has been dealt with. The kernel then grabs the sigframe from the stack, restores the process’s context and resumes the execution of the process.

This is the rough mental picture you should have:

test

 

Okay… but you still haven’t explained what SROP is..?

Well, if you insist…

The above process was designed so that the kernel does not need to keep track of what signals it has delivered. The kernel assumes that the sigframe it takes off the stack was legitimately put there by the kernel because of a signal. This is where we can trick the kernel!

If we can construct a fake sigframe, put it on the stack, and call sigreturn, the kernel will assume that the sigframe is one it put there before and will load the contents of the fake context into the CPU’s registers and ‘resume’ execution from where the fake sigframe tells it to. And that is what SROP is!

Well that sounds cool, show me!

First we have to set up a (valid) sigframe:

By valid sigframe, I mean a sigframe that the kernel will not reject. Luckily most architectures only examine a few parts of the sigframe to determine the validity of it. Unluckily, you will have to dive into the source code to find out which parts of the sigframe you need to set up for your architecture. Have a look in the function which deals with the syscall sigreturn (probably something like sys_sigreturn() ).

For a real time signal on a little endian powerpc 64bit machine, the sigframe looks something like this:

struct rt_sigframe {
        struct ucontext uc;
        unsigned long _unused[2];
        unsigned int tramp[TRAMP_SIZE];
        struct siginfo __user *pinfo;
        void __user *puc;
        struct siginfo info;
        unsigned long user_cookie;
        /* New 64 bit little-endian ABI allows redzone of 512 bytes below sp */
        char abigap[USER_REDZONE_SIZE];
} __attribute__ ((aligned (16)));

 

The most important part of the sigframe is the context or ucontext as this contains all the register values that will be written into the CPU’s registers when the kernel loads in the sigframe. To minimise potential issues we can copy valid values from the current GPRs into our fake ucontext:

register unsigned long r1 asm(“r1”);
register unsigned long r13 asm(“r13”);
struct ucontext ctx = { 0 };

/* We need a system thread id so copy the one from this process */
ctx.uc_mcontext.gp_regs[PT_R13] = r13;

/*  Set the context’s stack pointer to where the current stack pointer is pointing */
ctx.uc_mcontext.gp_regs[PT_R1] = r1;

 

We also need to tell the kernel where to resume execution from. As this is just a test to see if we can successfully get the kernel to resume execution from a fake sigframe we will just point it to a function that prints out some text.

/* Set the next instruction pointer (NIP) to the code that we want executed */
ctx.uc_mcontext.gp_regs[PT_NIP] = (unsigned long) test_function;

 

For some reason the sys_rt_sigreturn() on little endian powerpc 64bit checks the endianess bit of the ucontext’s MSR register, so we need to set that:

/* Set MSR bit if LE */
ctx.uc_mcontext.gp_regs[PT_MSR] = 0x01;

Fun fact: not doing this or setting it to 0 results in the CPU switching from little endian to big endian! For a powerpc machine sys_rt_sigreturn() only examines ucontext, so we do not need to set up a full sigframe.

Now we have to put it on the stack:

/* Set current stack pointer to our fake context */
r1 = (unsigned long) &ctx;

Finally, we call sigreturn:

/* Syscall – NR_rt_sigreturn */
asm(“li 0, 172\n”);
asm(“sc\n”);

 

When the kernel receives the sigreturn call, it looks at the userspace stack pointer for the ucontext and loads this in. As we have put valid values in the ucontext, the kernel assumes that this is a valid sigframe that it set up earlier and loads the contents of the ucontext in the CPU’s registers “and resumes” execution of the process from the address we pointed the NIP to.

Obviously, you need something worth executing at this address, but sadly that next part is not in my job description. This is a nice gateway into the kernel though and would pair nicely with another kernel vulnerability.  If you are interested in some more in depth examples, have a read of this paper.

So how can we mitigate this?

Well, I’m glad you asked. We need some way of distinguishing between sigframes that were put there legitimately by the kernel and ‘fake’ sigframes. The current idea that is being thrown around is cookies, and you can see the x86 discussion here.

The proposed solution is to give every sighand struct a randomly generated value. When the kernel constructs a sigframe for a process, it stores a ‘cookie’ with the sigframe. The cookie is a hash of the cookie’s location and the random value stored in the sighand struct for the process. When the kernel receives a sigreturn, it hashes the location where the cookie should be with the randomly generated number in sighand struct – if this matches the cookie, the cookie is zeroed,  the sigframe is valid and the kernel will restore this context.  If the cookies do not match, the sigframe is not restored.

Potential issues:

  • Multithreading: Originally the random number was suggested to be stored in the task struct. However, this would break multi-threaded applications as every thread has its own task struct. As the sighand struct is shared by threads, this should not adversely affect multithreaded applications.
  • Cookie location: At first I put the cookie on top of the sigframe. However some code in userspace assumed that all the space between the signal handler and the sigframe  was essentially up for grabs and would zero the cookie before I could read the cookie value. Putting the cookie below the sigframe was also a no-go due to the ABI-gap (a gap below the stack pointer that signal code cannot touch) being a part of the sigframe. Putting the cookie inside the sigframe, just above the ABI gap has been fine with all the tests I have run so far!
  • Movement of sigframe: If you move the sigframe on the stack, the cookie value will no longer be valid… I don’t think that this is something that you should be doing, and have not yet come across a scenario that does this.

 

For a more in-depth explanation of SROP, click here.

(Also posted this on https://sthbrx.github.io/)

Standard
Kernel, Linux

When you have no bootable kernels on a VM…

DON’T PANIC!

STEP ONE:

Shutdown your VM. If you are using virsh, try

virsh shutdown <vm-name>

which is equivalent to sending the shutdown command to your VM. Check if the VM actually shutdown with:

virsh list

If your VM is being stubborn, try:

virsh destroy <vm-name>

which is equivalent to pulling the power from your VM.

STEP TWO:

Ideally you would have saved a backup of your VM image when it was working… If you had the foresight to do this, then simply copy this into where your VM image is stored and reboot!

Otherwise, make a copy of your existing VM image and store it somewhere safe (in case we end up destroying the actual image…).

STEP THREE:

Mount the VM image as a filesystem!

There are multiple different ways to mount the various types of disk images out there. Here is how I mounted my qcow2 image:

Mount the nbd kernel module:

sudo modprobe nbd max_part=63

Check that it mounted correctly:

lsmod | grep nbd

Run parted to investigate the partition tables of your disk (so we know how to mount it):

sudo parted /dev/nbd0

In parted, run:

check p

you should see some output describing your partition table. For example:

Model: Unknown (unknown)
Disk /dev/nbd0: 26.8GB
Sector size (logical/physical): 512B/512B
Partition Table: gpt
Disk Flags:

Number   Start          End             Size   File system Name   Flags
1              1049kB      8389kB     7340kB                                      prep
2              8389kB     264MB     256MB             ext2
3              264MB      21.5GB       21.2GB                                       lvm

Partition 2 is the one that we want. Exit parted by typing ‘quit’.

Now we know which partition to boot:

sudo mount /dev/nbd0p2 /mnt/

cd /mnt

You should see your boot folder!

STEP FOUR:

Now copy across or edit any files you need!

STEP FIVE:

Unmount your disk:

sudo umount /mnt

Kill the process using qumu-nbd

ps -aux | grep qemu-nbd

sudo killall qemu-nbd

Remove kernel module:

sudo rmmod nbd

Now rerun your VM as per usual!

Standard