Nathan Gauer

Boursorama: auth flow & scraping

Sat, 16 Nov 2024 00:00:00 +0000

Introduction

My accounting software is useless without automatic transaction fetching. Open Banking, enabled by DSP2, is theoretically an option, but the official certification process is a major hurdle. Given that they offer a mobile and web app, I suspect there might be an API I can leverage.

Figuring out how this works might be fun, after all, the last bank auth process I looked into was… peculiar 🙃.

As most French banks, the authentication flow typically involves:

Entering a digits-only username.
Inputting a digits-only password using a visual keyboard.
Potentially validating a second factor via the bank’s app.

Before sending any login info, Boursorama requires you to do a few fixed requests to gather some magic cookies. There returned values seem quite stable for a given IP.

$ curl 'https://clients.boursobank.com/connexion/'
[...]
<script>
    document.cookie="__brs_mit=<128 bit hex key>; domain=." + window.location.hostname + "; path=/; ";
</script>
[...]

To continue, this key must be included in every subsequent request as the __brs_mit cookie. Doing the same request again, but providing __brs_mit yields 2 new cookies:

brsxd_secure=<some 142 char long key, not base64>
navSessionId=web<sha-256>

In addition to those, we also need a third value: form[_token]! This token can be found in the returned HTML page. It looks like a JWT token (b64, sections separated by a dot), but is not. This token will have to be returned with the input/password POST request.

Step 2: SVG based obfuscation

Since the beginning, no user information was required. It was simply a matter of making the right requests and collecting bits in the cookies or returned HTML.

Now comes the last hurdle: the keypad.

As usual, the user needs to type the password using a visual keyboard. No direct key input is allowed. Perhaps to prevent a keylogger from discovering your highly secure 8-digit password?

What’s interesting is that the request doesn’t contain the password itself, but rather a series of 3-letter groups. So if you type 12345567, you get NXS|GKY|KJE|YOL|JXA|JXA|YFM|YSP. The sequence changes with each page reload, but the digits remain unshuffled, and the same digits are always encoded the same way.

NXS|GKY|KJE|YOL|JXA|JXA|YFM|YSP
 1 | 2 | 3 | 4 | 5 | 5 | 6 | 7
                 ^   ^
                 same!

The idea is that the server sends down 10 SVG files, each associated with a 3-letter sequence. Then, when the user clicks on an SVG button, the JS records the associated letters and appends them to the “password”.

This SVG-group association can be found by loading https://clients.boursobank.com/connexion/clavier-virtuel?_hinclude=1 (don’t forget to include all the cookies we gathered so far).

On the returned HTML page, you’ll find a list of SVGs, each linked to a data-matrix-key attribute:

Now that we have 10 SVG images and their corresponding groups, how do we know what digits each image represents?

# SVG are always the same, and the path length is different for each digit.
B64_SVG_LEN_MAP = {
        419  : 0,
        259  : 1,
        1131 : 2,
        979  : 3,
        763  : 4,
        839  : 5,
        1075 : 6,
        1359 : 7,
        1023 : 8,
        1047 : 9,
}

key = B64_SVG_LEN_MAP[len(my_svg_path)]

Step 3: Loggin in!

Equipped with the magic cookies and a SVG-to-digit conversion method, we can delve into the login step!

The login request is a multipart form POST request. It requires a few fields to be accepted.

Some make sense:

clientNumber: the username/client ID.
password: the 3-letter chain we created by understanding the digit images.
matrixRandomChallenge: a long hex key gathered in the HTML along the keypad. Probably the key used to generate the 3-letters group, allowing the server to be stateless.
_token: one of the many magic values we got by fetching a particular URL (part 1, ‘form[_token]’)
ajx: always ‘1’
platformAuthenticatorAvailable: “-1”, I guess something to say if my device supports passkeys?

Some are just plain weird:

fakePassword: one instance of the • character for each digit in the password. So ‘••••••••’ since Boursorama enforces the password length to be 8.

And some are probably related to some analytics and can be discarded:

passwordAck: A JSON containing the timestamp of the click on each digit, and the X/Y coordinate of the said tap relative to the button.

Initially, I feared that this last field would require a more complex “human” check, such as emulating keypad layout and calculating realistic click delays based on button distances. However, it turns out that a simple {} is a sufficient value for passwordAck.

The final form request looks like this:

form[clientNumber]: <actual client number, plain text, e.g: 12341234>
form[password]: "CEF|UGR|O....E|IKR|KNE" # 3-key sequence we computed before.
form[ajx]: 1
form[platformAuthenticatorAvailable]: "-1"
form[passwordAck]: "{}"
form[fakePassword]: "••••••••"
form[_token]: <kinda JWT token, not quite, fetched from the previous steps>
form[matrixRandomChallenge]: <very long key, 13k characters, looks like B64>

This as POST request to `https://clients.boursobank.com/connexion/saisie-mot-de-passe’, along with the previously gathers cookies should yield us 2 final cookies:

brsxds_d6e4a9b6646c62fc48baa6dd6150d1f7 = <actual JTW token>
ckln<sha256> = <HTML quoted 2048-bit RSA?>

The first is a simple JWT token. But what’s intersting is the cookie name: brsxds_d6e4a9b6646c62fc48baa6dd6150d1f7! Did you know d6e4a9b6646c62fc48baa6dd6150d1f7 is the MD5 hash of prod ? 🙃 Turns out naming the cookie brsxds_prod wasn’t enough, they needed to hash the suffix.

The second cookie is a bit more mysterious. The name seems to be a SHA-256 hash prefixed with ckln. Not sure why. The value itself looks to be a twice URL-encoded 2048-bit base64 key, but I wasn’t able to figure out more. But as always: just add those to the next request, and everything works!

Step 4: Fetching my data

As any 90’s movie hacker would say: I’m in! Time to grab some transaction and account information to feed my software.

Unfortunately, Boursorama doesn’t appear to offer a JSON API for easy data access, it seems to rely heavily on Server-Side Rendering. To retrieve my account list, I fetched https://clients.boursobank.com/mon-budget/generate and parsed the HTML.

As for recent transactions, there’s at least a CSV exporter available:

params = {
        'movementSearch[selectedAccounts][]': account_id,
        'movementSearch[fromDate]': from_date.strftime('%d/%m/%Y'),
        'movementSearch[toDate]': to_date.strftime('%d/%m/%Y'),
        'movementSearch[format]': 'CSV',
        'movementSearch[filteredBy]': 'filteredByCategory',
        'movementSearch[catergory]': '',
        'movementSearch[operationTypes]': '',
        'movementSearch[myBudgetPage]': 1,
        'movementSearch[submit]': ''
}

url = 'https://clients.boursobank.com/budget/exporter-mouvements'
session = requests.Session()
resp = session.request('GET', url, cookies=cookies, params=params)

Note: if the range is invalid, or returned no results, the response is not a CSV anymore, but an HTML page showing an error message.

Final thoughts

As always with bank logins, I find this very convoluted, but not sure of the added benefit. In fact, most magic cookies were simply fetched from the server once, and sent back as-is in all subsequent requests, and the only challenge (SVG->key) is quite trivial.

I’d be curious to know the rational behind all that. Initialy I thought maybe the magic cookies are used to prevent some kind of MITM or replay attack? But unlike OVH which uses time-based request signatures, those keys seems to be quite stable.

In the future, I’d like to explore the mobile app, see if there is some JSON API I could use, because parsing HTML feels wrong.

I Hope you found this post interesting!

Banks, Keypad & Statements

Wed, 21 Feb 2024 00:00:00 +0000

The details of this article have been communicated to the bank, but after 6 months of silence, I’m assuming it is not an issue for them, and decided to release this (see timeline below).

I think they are breaking PSD2 regulation around strong authentication, but
I’m not an expert on that subject.

Introduction

When I was a child, I had a 10€ allowance per month. I remember keeping a small paper with all those transactions, but also planning future investment. For example, I knew I had to save for 8 years to afford my driving license.

Fast forward 2017, student, new flat, and thus the start of the great accounting spreadsheet™.

After 6 years, it became The Humongous Accounting Spreadsheet™.
Turns out, a single spreadsheet is not the ideal tool to track your every expenses across multiple countries. So here we are, with My Own Accounting Tool®.

It is fancy-enough, auto-categorizes most transactions, and can display pretty graphs.

Problem is, I still have to record transactions manually.

When I’m lucky, It’s a curl gathered from Firefox (DevTools > copy as cURL).
For others, a wonky regex-based python script to parse statements.

My goal: automatically fetching transactions directly from my bank account. This should reduce input mistake and accounting errors. My bank should have an API right?

The official API

The bank seems to have a public API: https://developer.lcl.fr/.
But as far as I understand, one needs to sign an agreement with the authorities or something, before getting some kind of certificate to sign requests.. Not going down that path tonight!

This bank also offers a website, so unless it’s full SSR, they should have some API I can plug into.

The other API

A quick look at the network requests, and here we are: https://monespace.lcl.fr/api/*!

The most interesting routes seems to be:

https://monespace.lcl.fr/api/login
https://monespace.lcl.fr/api/login/keypad
https://monespace.lcl.fr/api/login/contract
https://monespace.lcl.fr/api/user/accounts?type=current&contract_id=XXXXXXXX
https://monespace.lcl.fr/api/user/<account-id>/transactions

Those should be enough to fetch my own banking information.

To access my own data, I need to login.
For some unknown reason, banks in France LOVE weird SeCuRe visual keypads.
This bank doesn’t deviate: a 6-digit pin is the only password you need.

First surprising element: no 2FA by default? This bank does provide one (prompt on a trusted device), but it is only required for a few specific operations. I tried login on a blank browser, on a phone, with a new IP, and still, only the 6-digit password.

⚠ When traveling abroad, I noticed 2FA was required on the web page once, logging in from an already trusted device.
Rented a VPN, and tried my script in a few locations in France and Europe, and 2FA was never required. Not sure of the heuristic they chose, but since I can login from an untrusted location, and untrusted device, seems weak.

The 2 important network requests during the login are:

https://monespace.lcl.fr/api/login
https://monespace.lcl.fr/api/login/keypad

When you load the page, a first GET request is sent to api/login/keypad.
Upon login, a POST request is sent to api/login.

⚠ I redacted some parts of the request samples. The reason is I don’t know what those are, and if they contain secrets I shall not share.

`api/login/keypad` GET request

{
    "keypad": "13236373539383433303XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
}

keypad: A long, apparently random, digit-only sequence (partially redacted).

`api/login` POST request

{
   "callingUrl" : "/connexion",
   "clientTimestamp" : 1692997262,
   "encryptedIdentifier" : false,
   "identifier" : "XXXXXXXXXXX",
   "keypad" : "030303939303XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
   "sessionId" : "00000000000000000000001"
}

clientTimestamp: timestamp of the request.
encryptedIdentifier: always false, not sure why. Maybe something for plain HTTP requests?
identifier: the customer number.
keypad: A long, digit-only sequence (partially redacted). Maybe a challenge response?
sessionId: some client-side value derived from the timestamp. Seems to accept all numerical values as long as it respects some format.

Digit mangling

A large random number received, some client-side process with a keypad, and a large random number sent back. Some kind of challenge-response? Not exactly.

The keypad parameter is composed of 2 parts:

13236373539383433303: a sequence determining the order of the keys on the keypad.
XXXXXXXXX...: the random seed used to generate that order?

So what do my login request looks like with the code 011000 ?
"keypad": "030303939303XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

The repetition pattern looks familiar.

03 03 03 93 93 03 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
 0  0  0  1  1  0 ??

Yes, that’s the pin code, mangled digit by digit, and reversed. The mangling is a bit weird:

take the received keypad
reverse the string
parse digits, 2 by 2, as an hex value
take the last 10 pairs
interpret them as base-10
take the ascii char corresponding to the each value.
those are your keypad numbers

I spare you the JS handling the keypad, but here is the python code to login.

answer = get_json("https://monespace.lcl.fr/api/login/keypad")

keypad = answer['keypad']

# Weird mangling/obfuscation for the keypad values.
# The HEX digits, interpreted as base-10 are the keypad digits.
keys = [ chr(int(x, base=16)) for x in re.findall('..', keypad[::-1]) ][-10:]
seed = "".join([ chr(int(x, base=16)) for x in re.findall('..', keypad[::-1]) ][:-10])

password = input("Your 6 digit pin? ")
mangled = "".join([ str(keys.index(x)) for x in password ])
token = "".join([ str(hex(ord(x)))[2:] for x in (seed+mangled) ])[::-1]

payload = {
    'callingUrl': "/connexion",
    'encryptedIdentifier': False,
    'identifier': "<customer-id>",
    'keypad': token,
    'clientTimestamp': now,
    'sessionId': "<some-random-value>"
}

post_json("https://monespace.lcl.fr/api/login", payload)

Getting the transactions

Now that we are logged in, we want to list transactions.

Each transaction is tied to an account.
Each account is tied to a contract.
Each contract is tied to a user.

So to get my transactions, I need to get the contract, then get the account, and only then transactions.

The initial login request returns a few info:

{
    "accessToken": "<Bearer token>",
    "refreshToken": "<Refresh token>",
    "expiresAt": "<timestamp>",
    "multiFactorAuth": null,
    "userName": "<name>",
    "birthdate": "<birthdate>",
    "[...]"
    "contracts": [
        {
            "id": "<contract-id>",
            "[...]"
        }
    ],
}

As-is, the accessToken cannot be used to fetch transactions. Instead, it is used to get a second token. Token which authenticates requests made to a specific “contract”. I’m not sure how accounts are tied to “contracts”, but in my case, I have 1 contract tied to 1 account.

`api/login/contract` POST request

{
    "clientTimestamp": timestamp,
    "contractId": base64.b64encode(contract["id"].encode()).decode()[:-2]
}

Why is the contract ID base64 encoded? Maybe some code sharing with the user/accounts GET route?

`api/login/contract` response.

{
    "accessToken": "<another-token>",
    "refreshToken": "<refresh-token>",
    "expiresAt": "<timestamp>"
}

This access token can be used on 2 routes:

https://monespace.lcl.fr/api/user/accounts?type=current&contract_id=XXXXXXXX
https://monespace.lcl.fr/api/user/<account-id>/transactions

`api/user/accounts` GET request

This request takes 4 parameters:

type: the type of the contract/account to fetch?, Here set to current.
contract_id: the base64 encoded contract ID.
is_eligible_for_identity: false. Not sure what this is about.
include_aggregate_account: <boolean>

It returns some information about the fetched account:

{
    "total": "<balance-in-euro>",
    "accounts": [
        {
            "type": "current",
            "iban": "<the iban>",
            "amount": {
                "date": "2023-08-25T22:45:46.892+0200",
                "value": "<balance>",
                "currenty": "EUR"
            },
            "internal_id": "<internal-account-id>",
            "external_id": "<external-account-id>",
            "[...]"
        }
    ]
}

`api/user/<account-id>/transactions` GET request

This request takes 2 parameters:

contract_id: this time, the internal_id received in the previous request.
range: <int32>-<int32>. From-To range of transactions to fetch. 0 is the most recent transaction.

{
    "isFailover": "<boolean>",
    "accountTransactions": [
        {
            "label": "CB some shop",
            "booking_date_time": "1970-01-01T00:00:00.000Z",
            "is_accounted": "<boolean>",
            "are_details_available": "<boolean>",
            "amount": {
                "value": -5.32,
                "currency": "EUR"
            },
            "movement_code_type": "<code>",
            "nature": "<I/CARTE/VIREMENT SEPA RECU/PRELVT SEPA RECU XXX>"
        }
    ]
}

movement_code_type: not sure, sometimes absent, sometimes an int (like 948).
nature: seem to be a free-form field, as SEPA order text can be seen there.

Getting old transactions

The api/user/<account-id>/transactions request takes a range. But if this range contains any transaction older than 90 days, the request fails: 2FA is required to make such request.

Digging a bit, I found 2 other API routes:

api/user/documents/accounts_statements
api/user/documents/documents

Those routes have no limit on the dates.

WAIT, WHAT?

Yes, they do require 2FA to call https://monespace.lcl.fr/api/user/<account-id>/transactions for transactions older than 90 days, but PDF statements since the dawn of time? Sure, NO PROBLEM.

The returned values have this format:

[
    {
        "codsoufamdoc_1": "AST",
        "datprddoccli": "2020-12-02",
        "downloadToken": "<some-token>",
        "liblg_typdoc": "Some human-readable document title",
        "libsoufamdoc_1": "Some human-readable category"
    }
]

To download the PDF, a GET request with the downloadToken fetched in the previous request:

https://monespace.lcl.fr/api/user/documents/download?downloadToken=<token>

Final thoughts

No 2 factor authentication;

A 6-digit pin. Really?
Why isn’t 2FA enforced by default? Even my empty Twitter account is more secured.

Why is the pin code mangled?

Isn’t SSL enough to secure your payload?
This rot-13 like obfuscation really seems weak if that’s the worry.

Auth tokens remains valid for 21 days

The web session does auto-exit after ~30mn of inactivity.
But did you know the auth tokens remains valid for 21 days?

Anyway, I do have what I need to interoperate with my accounting application, and I can rest peacefully, knowing my personal information are safe 🙃.

All the information disclosed here are public, and freely accessible with any web browser. I was required to figure this out to build interoperability with my own software.

Disclosure timeline

28-08-2023: found those weaknesses, documented them.
01-09-2023: contacted the bank on twitter via private message to ask about this.
04-09-2023: contacted the bank by email since the twitter message hasn’t been replied to.
05-09-2023: received a twitter message saying “we received the email, we’ll reply”
21-02-2024: No news. Same behavior observed. Published this article.

Hosting this blog

Thu, 23 Feb 2023 00:00:00 +0000

This blog is simple: some .md files, generated to static HTML. No backend or complex CMS. It’s light, loads fast, and readable-enough on mobiles (except code-blocks). Versioning is done on git. But it had one drawback: “high” cost to publish.

Building is done using Jekyll, and then pushing files to an FTP server. Since I publish rarely, I had no warm setup. Sometimes my ruby installation was broken, sometimes some dependency were broken. Once built, pushing to the FTP was a mix of FTP fuseFS + rsync (My OVH hosting had to ssh/sshfs access). As always with manual intervention, error could happen!

Anyway, I had some free credits on GCP, so tried Cloud Builder (used it in the past to setup CIs), and quickly stopped. Goal was to simplify the whole process, and using GCP is not going the good direction.

Found out about Firebase, decided to give it a try (spoiler: blog is hosted on Firebase as of today). And it had everything I need: It’s fast, simple, and absolutely cheap for my use-case!

Deploying the website was simple:

$ firebase deploy

This combined with a GitHub workflow, spinning a ruby docker, building the website and pushing to firebase:

'on':
  push:
    branches:
      - master
jobs:
  build_and_deploy:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v2
      - name: Prepare tree
        run: 'mkdir build'
      - name: Build docker image
        run: 'cd docker && docker build -t builder . && cd ..'
      - name: Build website
        run: 'docker run -t --rm --mount type=bind,src=/home/runner/work/blog/blog,dst=/mnt/src --mount type=bind,src=/home/runner/work/blog/blog/build,dst=/mnt/output builder'
      - uses: FirebaseExtended/action-hosting-deploy@v0
        with:
          repoToken: '$'
          firebaseServiceAccount: '$'
          channelId: live
          projectId: blog-1234

This also brings another advantage: Github becomes my CMS. I can write a new article as long as I have some Github access. Which is quite convenient!

Sparse virtual textures

Wed, 27 Apr 2022 00:00:00 +0000

While working on parallax mapping, somebody told me about a cool presentation: Sparse virtual textures. The idea is quite simple: reimplement pagination in your shaders, allowing you to have infinite textures while keeping the GPU memory usage constant.

Goal was set: add SVT support to my renderer!

Step 1 - Hand-made pagination

Pagination overview

To understand how SVT works, it is useful to understand what pagination is.

On most computers, data is stored in the RAM. RAM is a linear buffer, and its first byte is at the address 0, and the last at address N.

For some practical reasons, using the real address is not very convenient. Thus some clever folks invented the segmentation, which then evolved into pagination.

The idea is simple: use a virtual address, that is translated by the CPU into the real RAM address (physical). The whole mechanism is well explained by Intel¹

This translation possible thanks to pagetables.

Translating every addresses into a new independant one is costly and not needed. That’s why they divided the whole space in pages. A page is a set of N contiguous bytes. For example, on x86, we often talk about 4kB pages.

What the CPU translate are page addresses. Each block is translated as a contiguous unit. The internal offset remains the same. This means for N bytes, we only have to store N/page_size translations.

Here on the left you have the virtual memory, divided in 4 blocks (pages). Each block is linearly mapped to an entry in the pagetable.

The mapping can be understood as follows:

Take your memory address.
- adress = 9416
Split it into a page-aligned value and the rest.
- 9416 => 8192 + 1224.
- aligned_adress = 8192
- rest = 1224
Take the aligned value, and divide it by the page size.
- 8192 / 4096 = 2
- index = 2
This result is the index in the pagetable.
Read the pagetable entry at this index, this is your new aligned address:
- pagetable[2] = 20480
Add the rest back to this address:
- physical_address = 20480 + 1224
You have your physical address.

Adding the page concept to the shader

To implement this technique, I’ll need to:

find which pages to load
load them in the “main memory”
add this pagetable/translation technique.

This could be done using compute shaders and linear buffers, but why not use textures directly? This way I can just add a special rendering pass to compute visibility, and modify my pre-existing forward rendering pass to support pagetables.

First step is to build the pagetable lookup system. This is done in GLSL:

take the UV coordinates
split them into page-aligned address, and the rest
compute page index in both X and Y dimensions
lookup a texture at the computed index (our pagetable)
add to the value the rest


Showing UV coordinates


Showing page-aligned UV coordinates

Computing visibility

The other advantage of pagination is the ability to load/unload parts of the memory at runtime. Instead of loading the whole file, the kernel only loads the required bits (pages), and only fetch new pages when required.

This is done using a pagefault:

User tries to access a non-yet loaded address.
CPU faults, and send a signal to the kernel (page fault).
The kernel determines if this access is allowed, and loads the page.
Once loaded, the kernel can resume the user program.

This mechanism requires hardware support: the CPU knows what a pagetable is, and has this interruption system. In GLSL/OpenGL, we don’t have such thing. So what do we do when interrupts don’t exits? We poll!

For us, this means running an initial rendering pass, but instead of rendering the final output with lights and materials, we output the page addresses. (Similar to the illustration image seen above).

This is done by binding a special framebuffer, and doing render-to-texture. Once the pass completed, the output texture can be read, and we can discover which pages are visible.

For this render pass, all materials are replaced with a simple shader:

#version 420 core

/* material definition */
uniform float textureid;
/* Size of a page in pixels. */
uniform float page_size;
/* Size of the pagetable, in pixels (aka how many entries do we have). */
uniform float pagetable_size;
/* Size in pixels of the final texture to load. */
uniform float texture_size;
/* Aspect ratio difference between this pass, and the final pass. */
uniform float svt_to_final_ratio_w; // svt_size / final_size
uniform float svt_to_final_ratio_h; // svt_size / final_size

in vertex_data {
    vec2 uv;
} fs_in;

out vec4 result;

/* Determines which mipmap level the texture should be visible at.
 * uv: uv coordinates to query.
 * texture_size: size in pixels of the texture to display.
 */
float mipmap_level(vec2 uv, float texture_size)
{
    vec2 dx = dFdx(uv * texture_size) * svt_to_final_ratio_w;
    vec2 dy = dFdy(uv * texture_size) * svt_to_final_ratio_h;

    float d = max(dot(dx, dx), dot(dy, dy));
    return 0.5f * log2(d);
}

void main()
{
    /* how many mipmap level we have for the page-table */
    float max_miplevel = log2(texture_size / page_size);

    /* what mipmap level do we need */
    float mip = floor(mipmap_level(fs_in.uv, texture_size));

    /* clamp on the max we can store using the page-table */
    mip = clamp(mip, 0.f, max_miplevel);

    vec2 requested_pixel = floor(fs_in.uv * texture_size) / exp2(mip);
    vec2 requested_page = floor(requested_pixel / page_size);

    /* Move values back into a range supported by our framebuffer. */
    result.rg = requested_page / 255.f;
    result.b = mip / 255.f;

    /* I use the alpha channel to mark "dirty" pixels.
     * On the CPU side, I first check the alpha value for > 0.5,
     * and if yes, consider this a valid page request.
     * I could also use it to store a "material" ID and support
     * multi-material single-pass SVT. */
    result.a = 1.f;
}

Once the page request list retrieved, I can load the textures in the “main memory”.

The main memory is a simple 2D texture, and page allocation is for now simple: first page requested gets the first slot, and so on until memory is full.


“Main memory” texture

Once the page allocated, I need to update the corresponding pagetable entry to point to the correct physical address. This is done by updating the correct pixel in the pagetable:

R & G channels store the physical address.
B is unused.
A marks the entry as valid (loaded) or not.


Pagetable texture

Rendering pass

The final pass is quite similar to a classic pass, except instead of binding one texture for diffuse, I bind 2 textures: the pagetable, and the memory.

bind the 3D model
bind the GLSL program
bind the pagetable and main-memory textures.

At this stage, I can display a texture too big to fit in RAM & VRAM.

Step 2: MipMapping

If you look at the previous video, you’ll notice two issues:

Red lines showing up near the screen edges.
Page load increase when zooming out.

First issue is because texture loading doesn’t block the current pass. This means I might request a page, and not have it ready by the time the final pass is ran. I could render it as black, but wanted to make it visible.

The second issue is because I have a 1:1 mapping between the virtual page size and the texture page size. Zooming out to show the entire plane would require loading the entire texture. Texture which doesn’t fit in my RAM.

The solution to both these issues are mipmaps.

A page at mipmap level 0 covers page_size pixels.
A page at mipmap level 1 covers page_size * 2 pixels
…
A page at mipmap level N covers the whole texture.

Now, I can load the mipmap level N by default, and if the requested page is not available, I just go up in the mip levels until I find a valid page.

Adding mipmaps also allow me to implement a better memory eviction mechanism:
I can now replace 4 pages with one page a level above.
So if I’m low on memory, I can just downgrade some areas, and save 75% of my memory.

Finally, MipMapping reduces the bandwidth requirements: if the object is far, why load the texture in high resolution? A low-resolution page is enough:

less disk load.
less memory usage.
less latency (since there is less pages to load).


Showing physical addresses with MipMapping

Step 3: Complex materials

The initial rendered had PBR materials. Such material had not only an albedo map, but also normal and roughness+metallic maps. To add new textures, several options:

New memory textures, new pagetable texture, new pass.
simple
requires an additional pass. This is not OK.
Same memory texture, same pagetable texture.
Each page contains in fact the N textures sequentially. So when one page is loaded, N textures are queried and loaded.
Easy to implement, but I have to load N textures.
Same memory texture, multiple pagetable textures.
pagetables are small, 16x16 or 32x32. Overhead is not huge.
I can unload some channels for distant objects (normal maps by ex).
Drawback is I have now N*2 texture sampling in the shader: one for each texture and its associated pagetable.

Because I like the flexibility of this last option, I chose to implement it. In the final version, each object has 4 textures:

memory (1 mip level)
albedo pagetable (N mip levels)
roughness/metallic pagetable (N mip levels)
normal pagetable (N mip levels)

In the following demo, page loading is done in the main thread, but limited to 1 page per frame, making the loading process very visible.

Bottom-left graph shows the main memory.
Other graphs show the pagetables and their corresponding mip-levels.

Page request : subsampling, random and frame budget.

For each frame, I need to do this initial pass to check texture visibility. Reading this framebuffer on the CPU between each frame is quite slow, and for a 4K output, this is prohibitively expensive.

The good news is: I don’t need a 4K framebuffer in that case! Pages are covering N pixels, so we can just reduce the framebuffer size and hope our pages will still be requested!

The demo above is using a 32x32 framebuffer. Which is very small. If done naïvely, this wouldn’t work: some pages would be caught between 2 rendered pixels, and never loaded.


8x8 framebuffer, no jitter.

A way to solve that is add some jitter to the initial pass. The page request viewpoint is not exactly the camera’s position, but the camera’s position + some random noise.

This way, we can increase coverage without increasing the framebuffer size.


8x8 framebuffer, jitter.

See Intel Architectures Developer’s Manual: Vol. 3A, Chapter 3 ↩

Noise, blur and neural networks

Wed, 13 Apr 2022 00:00:00 +0000

I never experimented with machine learning or denoising. I guess having obscure matrices combined together to produce some result scared me a bit.. Surprising for someone who loves computer graphics… 🙃
After failing an interview for an ML-related position (surprising?) I thought enough is enough, time to play catch-up!

For this project, I started with the basics: Andrew NG ML course. After a couple days — and obviously becoming the greatest ML expert in the world — I decided to tackle the easiest problem ever: image denoising!

The goal

Denoising is a complex field, and some very bright people are making a career out of it. Not my goal!

Here I’ll try to explore some classic denoising techniques, implement them, and once used to some of the problems, build a custom model to improve the result.

The input:

I believe this should be a good candidate:

has a flat shape to check edge preservation.
has some “noise” to keep (foliage).
has some small structured details (steel beams).
has smooth gradients (sky).

Step 1 - sanity check

From Wikipedia:

noise is a general term for unwanted […] modifications that a signal may suffer

The graph above represents a line of pixels being part of a smooth shade. In red are 2 bad pixels. They are bad because they interrupt the smoothness of our graph, and thus are perceived as noise.

How can we remove some outliers in that case? Averaging! Each pixel value is averaged in regard to its neighbors. In this case, this would help reduce perceptible noise.

  foreach x, y in image
    neighbors = extract_window_around(image, x, y, window_size=10)
    res = average(neighbors)
    image.set(x, y, res)

But in real life, that’s terrible..

The reason for this poor performance is we don’t discriminate valid details from noise. We loose our edges, and all details are lost.

Step 3 - Better average - YUV vs RGB

The previous image was generated by averaging RGB values using a 10-pixels sliding window. Because it was averaging RGB values, it mixed colors. As result, edges were blurred in a very perceptible way, leading to an unpleasant result.

YUV is another color representation, splitting the channels not as red, green, and blue, but color, and luminosity. Colors are represented using polar coordinates, and luminosity is a single linear value.

If we look at the sky, the noise doesn’t seem to alter the color a lot, only the brightness of the blue. So averaging using the same window, but only on the luminance component should give better results:

Step 4 - selective average

Using YUV vs RGB helped: the sky looks fine, and the green edges look sharper. Sadly, the rest of the image looks bad. The reason is that I still use the same window size for the sky and the tower.

I can improve that solution using a new input: an edge intensity map. Using the well known Sobel operator I can generate the list of areas to avoid.

  edge_map = sobel(image)
  foreach x, y in image
    window_size = lerp(10, 1, edge_map.at(x, y))
    neighbors = extract_window_around(image, x, y, window_size)
    res = average(neighbors)
    image.set(x, y, res)

✅ The square edges are preserved.
✅ The sky blur is gone
✅ The Eiffel Tower’s edges seem preserved.
❌ Artifacts visible in the sky (top-right)
❌ The foliage texture is lost.
❌ The metallic structure lost precision.
❌ The grass mowing pattern is completely lost.

Step 5 - ML-based noise detection

In the previous step, I tried to discriminate areas to blur and keep as-is. The issue is my discrimination criteria: edges. I was focusing on keeping edges, but lost good noise like the foliage.

So now I wonder, can I split good noise from bad noise using a classification model?

  foreach x, y in image
    window = extract_window_around(image, x, y, window_size)
    bad_noise_probability = run_model(window)
    blur_window_size = lerp(1, 10, bad_noise_probability)
    res = average_pixels(image, x, y, blur_window_size)
    image.set(x, y, res)

For this model, I tried to go with a naïve approach:

select a set of clean images
generate their noisy counterpart in an image editor
split these images in 16x16 pixel chunks.

Those would represent my training & test set (6000 items and 600 items). The goal is now from a 16 pixel window, determine if the pixel belongs to noise, or belongs to some details.

Then, I would iterate over my pixels, extract the 16x16 window around, run the model on it, and use this probability to select my blur window. My guess is that we should now be able to differentiate foliage from sky noise.

Here is the model output: in red the parts to clean, in black the parts to keep.

And here is the output:

✅ Edges are preserved.
✅ Steel structure is clear in the middle.
✅ Left foliage looks textured.
❌ Right foliage shadows are still noisy.
❌ Some areas of the steel structure are blurred.
❌ Sky has artifacts.

The model training set is composed of only ~6000 chunks extracted from 4 images (2 good, 2 noisy). Training the same model on a better dataset might be a first solution to improve the noise classification.

This result seems better than the bilateral filtering, so I guess that’s enough for a first step into the ML world. I will stop there for now, and move on to the next project!

CTF Write-up: Sogeti 2019 - BadVM

Fri, 01 Mar 2019 00:00:00 +0000

Some friends were registered to this CTF, and since I had some days off, I decided to work a bit on one RE exercise.

The binary is called BadVM:

[nathan@Jyn badvm]$ ./badvm-original
### BadVM 0.1 ###

Veuillez entrer le mot de passe:
toto
Ca mouline ...
Plus qu'un instant ... On avait la réponse depuis le début en faite :>
Perdu ...

It is a stripped, ELF 64 PIE binary. Time to start Binary Ninja. This binary has no anti-debug, nor packing techniques. Just some calls to sleep. Once these calls NOPed, we can start reversing the VM.

The VM is initialized in the function I called load_vm (0xde6). Then, the function at 0xd5f is called, let’s call it vm_trampoline.

This function will choose the next instruction to execute. Load it’s address in rax and call it. vm_trampoline is called at the end of each instruction. Thus, each instruction is a new entry in the backtrace.

This means, when returning from the first call to vm_trampoline, we can read the result and return it. This takes us back to load_vm, and result is checked.

In case of an invalid character in the password, we have an early-exit. Input is checked linearly, no hash or anything, Thus instruction counting works well.

Since I was on holidays, I decided to experiment a bit with lldb, and write a instrument this VM using its API.

Reversing the VM

This VM uses 0x300 bytes long buffer to run. Some points of interest:

0x4: register A (rip)
0x5: register B
0xFF: register C (result)
0x2fc: register D
0x2fe: register E (instruction mask?)
0x32: password buffer (30 bytes)
0x2b: data buffer (xor data, 30 bytes)
0x200: data start (binary’s .data is copied in this area)

Instruction are encoded as follows:

To select the instruction, the VM contains a jump-table.

Here one of the instructions (a ~GOTO):

Final note: each instruction/function has the following prototype:

Instrumenting using LLDB

This VM does not check its own code, thus we can freely use software breakpoints. The code is not rewritten, thus offsets are kept. This allow us to simply use LLDB’s python API to instrument and analyse the VM behavior.

First step, create an lldb instance:

def init():
    dbg = lldb.SBDebugger.Create()
    dbg.SetAsync(True)
    console = dbg.GetCommandInterpreter()

    error = lldb.SBError()
    target = dbg.CreateTarget('./badvm', None, None, True, error)
    # check error

    info = lldb.SBLaunchInfo(None)
    process = target.Launch(info, error)
    print("[LLDB] process launched")

Now, we can register out breakpoints. Since vm_trampoline is called before each instruction, we only need this one:

    target.BreakpointCreateByAddress(p_offset + VM_LOAD_BRKP_OFFSET)

Now, we can run. To interact with the binary, we can use LLDB’s events. Registering a listener, we can be notified each time the process stops, or when a breakpoint is hit.

listener = dbg.GetListener()
event = lldb.SBEvent()

if not listener.WaitForEvent(1, event):
    continue

if event.GetType() != EVENT_STATE_CHANGED:
    # handle_event(process, program_offset, vm_memory, event)
    continue

regs = get_gprs(get_frame(process))
if regs['rip'] - program_offset != address:
    print("break location: 0x{:x} (0x{:x})".format(
          regs['rip'] - program_offset, regs['rip']))

To read memory, or registers, we can simply do it like that

process.ReadUnsignedFromMemory(vm_memory + 0, 1, err),

process.selected_thread.frame[frame_number].registers
# registers[0] contains general purpose registers

Now we can implement a pretty-printer to have “readable” instructions. Once everything together, we can dump the execution trace:

mov [0x00], 0xff
mov [0x01], 0x01
mov tmp, [0x00]  	# tmp=0xff
mov [tmp], [0x01]	# src=0x1
mov [0x00], 0x0b
mov [0x01], 0x1d
mov tmp, [0x00]  	# tmp=0xb
mov [tmp], [0x01]	# src=0x1d
mov [0x01], 0x0b
mov tmp, [0x01]  	# tmp=0xb
mov [0x00], [tmp]	# [tmp]=0x1d
mov r5, [0x00]
sub r5, [0x0a]   	# 0x1d - 0x0 = 0x1d
if r5 == 0:
    mov rip, 0x2d
mov [0x01], 0x0a
[...]

Now, we can reverse the program running in the VM:

def validate(password, xor_data):
    if len(password) != len(xor_data):
        return -1

    D = 0
    for i in range(len(xor_data)):
        tmp = (D + 0xAC) % 0x2D
        D = tmp
        if xor_data[i] != chr(ord(password[i]) ^ tmp):
            return i

    return len(xor_data)

And we get the flag:

SCE{1_4m_not_4n_is4_d3s1yn3r}

Conclusion

This VM has no anti-debug, packing or anything special. But it was a funny binary to reverse. To instrument the VM, lldb is useful, but using DynamiRIO would be a more elegant method.

3D engine - Parrallax Mapping with self-shadows

Thu, 28 Feb 2019 00:00:00 +0000

Working on my 3D game engine is the perfect occasion to reimplement classic algorithms. On today’s menu: self-shadowed steep parrallax-mapping First step, get the classic steep parrallax-mapping.

Here a two good links to implement this algorithm:

Steep parrallax-mapping allows us to get a pretty good result (10 samples):

But something is missing. Let’s implement self-shadows.

Self shadows are only computed on directional lights. The algorithm is very simple.

convert light direction in tangent space
compute steep parrallax-mapping
from the resulting coordinate, ray-march towards the light
If there is an intersection, reduce exposition

And then, TADAA

Shader code available here

(2 steps are more than enough for this part.)

Vulkan-ize Virglrenderer - experiment

Tue, 24 Jul 2018 00:00:00 +0000

Virglrenderer provides OpenGL acceleration to a guest running on QEMU.

My current GSoC project is to add support for the Vulkan API.

Vulkan is drastically different to OpenGL. Thus, this addition is not straight-forward. My current idea is to add an alternative path for Vulkan. Currently, two different states are kept, one for OpenGL, and one for Vulkan. Commands will either go to the OpenGL or Vulkan front-end.

For now, only compute shaders are supported. The work is divided in two parts: a Vulkan ICD in MESA, and a new front-end for Virgl and vtest.

If you have any feedback, do not hesitate !

This experiment can be tested using this repository. If you have an Intel driver in use, you might be able to use the Dockerfile provided.

Each part is also available independently:

GSoC 2018 - Vulkan-ize Virglrenderer

Thu, 12 Jul 2018 00:00:00 +0000

Several months ago started the GSoC 2018. Once again, I found a project which got my attention.

Vulkan-ize VirglRenderer

Virglrenderer is a library designed to provide QEMU guests with OpenGL acceleration. It is composed of several components:

a MESA driver, on the guest, which generates Virgl commands
a lib, on the host, which takes virgl commands and generated OpenGL calls from it.

If you want to read more: 3D Acceleration using VirtIO.

This library was built with OpenGL in mind. Today, Vulkan is correctly supported, and is becoming a new standard. It might be time to bring Vulkan to QEMU’s guests !

To do so, we will need to work on two components:

A Vulkan ICD. Writting one for MESA sounds like a good idea.
A Vulkan back-end for Virglrenderer.

Now, we can face the first issue: Vulkan is not designed with abstraction in mind. The time of the old GlBegin/glVertex is kinda dead.

If we want to avoid any unnecessary abstraction, we cannot easily reduce the amount of calls made to the API. Thus, the vast majority of the VK calls will be forwarded to the host. However, there is some area in which we can bend the rules a bit.

The rest of this post contains the same content as the announce email (virgl ML).

Project status

Several Vulkan objects can be created
Memory can be mapped and altered on the client.
Changes are written/read to/from the server on flush/invalidation
Basic features for command buffers are supported.

As a result, a sample compute shader can be ran, and the results can be read.

I only use vtest for now. The client part lies in mesa/srv/virgl.

Current behavior

To compile virglrenderer with vulkan, the option –with-vulkan is needed. Running the server as-is does not enable Vulkan. And for now, Vulkan cannot be used in parallel with OpenGL (Issue #1). To enable Vulkan, the environment variable VTEST_USE_VULKAN must be set.

Initialization:

The client driver is registered as a classic Vulkan ICD. When the loader call icdNegociateLoaderICDInterfaceVersion, the driver connects to the server. On failure, the driver reports as an invalid driver.

Once connected, the ICD will fetch and cache all physical devices. It will also fetch information about queue, memory and so. Physical devices are then exposed as virtual-gpus. Memory areas are showed as-is, except for the VK_MEMORY_PROPERTY_HOST_COHERENT bit, which is disabled. This forces the application to notify every modification made to a mapped memory.

The object creation part relies heavily on API-Forwarding. For now, I don’t see how I could avoid that.

Memory transfers

Once basic objects are created, the client will ask to map some memory. For now, no clever thing is done. The ICD will provide a buffer. On flush, a transfer command is issued. Virglrenderer will then map the corresponding memory region, write/read, and unmap it. A memory manager could be used on the server in the future to avoid mapping/unmapping regions each time a transfer occurs.

Commands and execution

Command pool creation is forwarded to the server. For now, a command buffer is attached to its pool. To retrieve a command buffer from a handle, I need to know from which pool it came from. (Issue #2) Command buffer creation is also forwarded to the server.

Command buffers state is managed on the client. Each vkCmd* call will modify an internal state. Once vkEndCommandBuffer is called, the state is sent to the server. The server will then call corresponding vkCmd* functions to match retrieved the state.

Code generation

Vulkan entry points are generated at compile time. Heavily inspired from Intel’s entry-point generation. However, since object creation relies on API-Forwarding, I started to work on a code generator for these functions.

Using a json, the interesting informations are outlined. Then a Python script will generate functions used to forward object creation to the vtest pipe. Even-though the Vulkan API seams pretty consistent, some specific cases and time constraints forced me to abandon it.

This script is still available in the mesa/src/virgl/tools and virglrenderer/tools folder, but is lacking features. Also, since I had different needs on both sides of vtest, scripts diverge a lot. The most recent version is the Virglrenderer one. It’s a second iteration, and it might be easier to work with.

In the current state, I use it to generate a skeleton for vtest functions, and then fixes the implementation. In the future, it could save us some time, especially if we use the same protocol for VirtIO commands.

Issues

1: (Virglrenderer) Vulkan cannot be used next to OpenGL.

There is no reason for it except a badly though integration of the vulkan initialization part into virglrenderer.

2: (Virglrenderer) Command buffers are scattered into several pools

Command buffers are scattered into several pools the client created. To fetch a command buffer vk-handle, I need to first fetch the corresponding pool from a logical device, then fetch the command buffer. Since VirtIO ant Vtest provides a FIFO, maybe we could drop the command pool creation forwarding. Use only one pool per instance, and thus simplify command buffers lookups.

3: (MESA) Vtest and VirtIO switch is not straightforward right now.

An idea could be to add a level between vgl_vk* functions an vtest. vgl_vk* function would still manage the state of the ICD. the mid-layer would convert handles and payload to a common protocol for both VirtIO and Vtest. (Both could use vgl handles and some metadata). Then, a backend function, which would choose between vtest and virtio.

The handles could be either forwarded as-is (vtest case) Or translated to real virgl handles in the case of a kernel driver which could do a translation, or check them. But the metadata should not change.

4: (Virglrenderer/MESA) vtest error handling is bad.

Each command sends a result payload, and optionally, data. This result payload contains two informations. An error code, and a numerical value. Use as a handle, or a size. On server failure, error-codes should be used.

5: bugs, bugs and bugs.

This project is absolutely NOT usable right now.

Next steps

My first step should be to rebase this project onto the current virglrenderer version, and rewrite the history. In the mean time, rewrite the initialization part to allow both OpenGL and Vulkan to be ran. Then, fix the vtest/virtio architecture. Add this new mid-layer. Once refactorized, I should work on the error handling for client-server interactions.

Once in a sane state, other issues will have to be addressed.

How to test it

There is a main repo used to build and test it rapidly. In it, a bash script and a dockerfile (+ readme, todo)

The bash script in itself should be enough. But if the compilation fails for a reason, the dockerfile could be used.

repository

The README provided should be enough to make the sample app run.

Repositories

Vulkan API search engine

Sat, 16 Jun 2018 00:00:00 +0000

Currently working on a Vulkan extension for VirglRenderer, I need to grep the API all the time. The official documentation gives me two options:

search the Vulkan spec (huge PDF)
use my browser custom engine feature and play with Khronos’ registry URL’s

The first is painful, and the second too strict (case sensitive).

Recently, I also went to an Algolia hosted meeting. Their search engine API looked good, and in my case, it’s free!

Thus, I took a couple hours off from my GSoC, and crafted this thing: a dirty Vulkan API search engine.

Edit 2024-04-02:

This utility had no users for a year. Algolia has scheduled the index deletion.

Its index is very outdated (Vulkan 1.0, very few KHR/vendor extensions).

The official Vulkan documentation has improved, making this utility obsolete.

For those 3 reasons, I am sunsetting this utility.

Raytracing 2 - KD-Tree and Photons

Wed, 02 May 2018 00:00:00 +0000

Last ray/path-tracers I did were simple. No acceleration datastructure, no complex lighting methods. And, I never tried GO.

Raytracing & KD-Trees

This tracer only supports triangles. I wanted to keep it simple.
Drawback: rendering a sphere was slow. Thus, Instead of storing my tris in an array, I stored them in a KD-Tree.

A KD-Tree is a tree based data-structure. Each node has a bouding box, and each tri contained in the node or in the children is in that bounding box.
This enable our tracer to quickly discard branch of a model which won’t cross our ray.

Since I wanted to visualized my tree, I implemented a CPU rasterizer in this tracer. Here is a rendering showing the bounding boxes:

Clean output

This project is far from finished. I still need to support indirect lighting and maybe use another shading model.

Code available on GitHub

CAN bus reverse on a Toyota Yaris

Wed, 28 Feb 2018 00:00:00 +0000

Talking with Cars

During my last internship, a coworked had a Toyota Yaris (2007). This car has an OBD-2 plug, and the owner was curious about what we could do with it. We had access to a simple CAN-bus probe, and some spare time.

Press & Seek

The first step is to understand what parts a linked to what packets. Our approach was to sort packets by IDs, and highlight changing bytes. Then, touch everything in the car we could think of. Once some basic informations where figured out, we could show some graphs.

Talking with Cars

Stanislas, another student, worked on a fake gamepad using his Fiat500 can packets. The code base was in Python, and all values were hardcoded. We could easily improve the architecture by implementing a src->sink model inspired from GStreamer’s.

All done. PR has been merged, and here is the repo: Repository

Raytracing & Pathtracing

Thu, 04 Jan 2018 00:00:00 +0000

Another project I’ve been working on during my daily commute. A raytracer(left) and a pathtracer(right).

Both available on GitHub

(Not the same Cornell box)

GSoC 2017 - 3D acceleration using VirtIOGPU

Sun, 27 Aug 2017 00:00:00 +0000

Several months ago started the GSoC 2017. Among all the projects available one got my attention:

Add OpenGL support on a Windows guest using VirGL

In a VM, to access real hardware, we have two methods: passthrough, and virtualization extensions (Intel VT-x, AMD-V..). When it comes to GPUs possibilities drop down to one: passtrough. Intel has a virtualization extension (GVT), but we want to support every devices. Thus, we need to fall-back to a software based method.

Emulation ? Since we want 3D acceleration, better forget it
API-forwarding ? This means we need to have the same OpenGL API between guest host, also no.
Paravirtualization ? Yes !

Since a couple years, VirtIO devices became a good standard on QEMU. Then, Dave Airlie started to work on VirGL and a VirtIO-gpu. Both help provide a descent virtual-GPU which rely on the host graphic stack.

This article will present VirtIO devices, and what kind of operations a guest can do using VirGL.

I also invite you to read a previous article I wrote about Linux’s graphic stack

VirtIO devices

Since we will use a VirtIO based device, let’s see how it works. First, these devices behave as regular PCI devices. We have a config space, some dedicated memory, and interruptions. Second very important point, VirtIO devices communicate with ring-buffers used as FIFO queues. This device is entirely emulated in QEMU, and can realize DMA transfers by sharing common pages between the guest and the host.

Communication queues

On our v-gpu, we have 2 queues. One dedicated to the hardware cursor, and another for everything else. To send a command in the queue, it goes like this:

guest: allocate pages on the host
guest: send a header and pointers to our physical pages (guest POV) in the ring buffer.
guest: send an interruption
VMExit
host: QEMU read our header and pointers. Translate addresses to match local virtual address range.
host: read the command, execute it
host: write back to ring buffer
host: send interruption
guest: handle interruption, read ring buffer and handle answer

VirGL

VirGL can be summed up as a simple state-machine, keeping track of resources, and translating command buffers to a sequence of OpenGL calls. It exposes two kinds of commands: let’s say 2D and 3D.

2D commands are mainly focused on resources management. We can allocate memory on the host by creating a 2D resource. Then initialize a DMA transfer by linking this resource’s memory areas to guest’s physical pages. To ease resource management between applications on the guest, VirGL also adds a simple context feature. Resource creation is global, but to use them, you must attach them to the context.

Then, 3D commands. These are close to what we can find in a API like Vulkan. We can setup a viewport, scissor state, create a VBO, and draw it. Shaders are also supported, but we first need to translate them to TGSI; an assembly-like representation. Once on the host, they will be re-translated to GLSL and sent to OpenGL.

You can find a part of the spec on this repository

OpenGL on Windows

Windows graphic stack can be decomposed as follows:

Interresting parts are:

OpenGL ICD (Installable client driver):

This is our OpenGL implementation -> the state machine, which can speak to our kernel driver.

GDI.dll:

A simple syscall wrapper for us.

D3D Subsystem:

First part of the kernel graphic stack. It exposes a 3D and 2D API. Since we are not a licensed developer, let’s try to avoid this. From the documentation, we have a some functions to bypass it: DxgkDdiEscape is one. This functions takes a buffer, a size, and lets it pass trough this subsystem, directly to the underlying driver.

DOD (Display Only Driver)

Our kernel driver. This part will have to communicate to both kernel/ICD and VirtIO-gpu.

OpenGL State-Tracker

OpenGL rely on a state machine we have to implement. Let’s start by drawing on the frame-buffer.

We start a new application, want to split it from the rest. So we start by creating a VirGL context. Then create a 2D resource (800x600 RGBA seams great), and attach it to our VGL-context.

We might want to draw something now. We have two options, either use the 3D command INLINE_WRITE, or DMA. Using INLINE_WRITE means sending all our pixels through a VirtIO queue. So let’s use DMA !

We start by allocating our memory pages on the guest.
Then, send physical addresses to VirGL (guest POV)
VirGL will translate PA addresses to local virtual addresses, and link these pages to our resource.
Back to the guest, we can write our pixels to the frame-buffer.
To notify the V-gpu, we use the TRANSFER_TO_HOST_2D command, which tells QEMU to sync resources.

Now, let’s draw some pixels on this frame-buffer. We will need :

create an OpenGL context
setup our viewport and scissor settings (ie: screen limits)
create a VBO
link the VBO to a vertex/normals/color buffer
create vertex and frag shaders
setup a rasterizer
setup the frame-buffer to use the one we created earlier
create a constant buffer
send the draw call

A 3D Command is a set of UINT32. The first one is used as a header, followed by N arguments. A command buffer can contains several commands stacked together in one big UINT32 array.

Earlier, we created resources in VGL-Contexts. Now we will need 3D objects. These are created sending 3D commands, and are not shared between VGL contexts. Once created, we have to bind them to the current opengl-context.

Now, if everything goes well, we should be able to display something like that:

Once more, explaining all the commands would be uninteresting, but there is a spec for that !

If you are still interested, here are couple of links:

GIST to present the project
DOD Driver: The kernel driver needed on the Windows guest to communicate with the VirtIO-gpu
ICD Driver: opengl32.dll, the userland driver including a basic state-tracker:
VirGL Reference : partial reference of VirGL 2D and 3D commands

Talk LSE-Week - QEMU and Virgl3D

Thu, 20 Jul 2017 00:00:00 +0000

This talk presented my ongoing project at this time:
Implement an OpenGL driver for Windows working with VirtIO-gpu.

The slides are available HERE

Linux graphic stack

Sat, 13 May 2017 00:00:00 +0000

In January 2017, results arrived. I was accepted at the LSE, a system laboratory in my school. We were 4, and had to find a new project to work on. One wanted to work on the linux kernel security, another on Valgrind, and then, there is me. I didn’t knew how to start, but I wanted to work on something related to GPUs.

My teacher arrived, and explained the current problem with Windows and QEMU: we don’t have any hardware acceleration. Might be useful to do something about it ! I was not ready…

The first step was to understand Linux graphic stack, and then find out how Windows could have done it. Finally, how we can bring this together using Virgl3D and VirtIO queues.

This article will try present you a rapid overview of the graphic stack on Linux. There already is some pretty good articles about the userland part, so I won’t focus on that, and put some links.

OpenGL 101

Let’s begin with a simple OpenGL application:

int main(int argc, char** argv)
{
    glutInit(&argc, argv);
    glutInitWindowSize(300, 300);
    glutCreateWindow("Hello world :D");

    glClear(GL_COLOR_BUFFER_BIT);
    glBegin(GL_TRIANGLE);
        glVertex3f(0.0, 0.0, 0.0);
        glVertex3f(0.5, 0.0, 0.0);
        glVertex3f(0.0, 0.5, 0.0);
    glEnd();
    glFlush();
    return 0;
}

This is a non working dummy sample, for the idea

As we can see, there is three main steps:

Get a window
Prepare our vertices, data…
Render

But how can we do that ?

Linux graphic stack

Level 1: Userland, X and libGL

The first part of our code looked like this:

glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE);
glutInitWindowSize(300, 300);
glutInitWindowPosition(100, 100);

But in fact, actions can be resumed to something like this:

CTX = glCreateContext()
CONNECTION = xcb_connect()
xcb_create_window(CONNECTION, PARAMS, SURFACE, WINDOW)

What ? a connection, a context ?

To manage our display, Linux can use several programs. A well known is the X server. Since it’s a real server, we have to connect to it first before being able to request anything. To ease our work, we will use the lib XCB. Once a window is created, any desktop manager compatible with X will be able to display it. For more informations about an OpenGL context -> Khronos wiki

Meet Mesa

Mesa is an implementation of OpenGL on Linux. Our entry point is libGL, just a dynamic library letting us interface with the openGL runtime. The idea is the following:

libGL is used by an OpenGL application to interact with Mesa
Generic OpenGL state tracker. Shaders are compiled to TGSI and optimized
GPU layer : A translation layer specific to our graphic chipset
libDRM and WinSys: an API specific to the kernel, used interface with the DRM
OpenGL state tracker: from basic commands like GlBegin GlVertex3 and so on, Mesa will be able to generate real calls, to create command buffers, vertex buffers, etc… Shaders will be compiled into an intermediate representation: TGSI. A first batch of optimizations in done on this step.
GPU layer: We now need to translate TGSI shaders to something our GPU can understand, real instructions. We will also shape our commands for a specific chipset.
libDRM and WinSys: We send this data to the kernel, using this interface

With this architecture, if I want to add a support to my own graphic card, I will have to replace one part : the GPU layer

For more informations about Mesa and Gallium -> Wikipedia Another good article on the userland part -> Igalia blog

Welcome to KernelLand !

Meet the DRM

DRM: Direct Rendering Manager. This is more or less an IOCTL API composed of several modules. Each driver can add some specific entry points, but there is a common API designed to provide a minimal support. Two modules will be described: KMS and the infamous couple TTM & GEM.

Meet KMS

Remember the first step of our OpenGL application ? Ask for a window, getting a place to put some fancy pixels ? That’s the job of the KMS: Kernel Mode-setting.

A long time ago, we used UMS: user mode setting. The idea was to manage our hardware directly from userland. Problems: every application needed to support all the devices. It means a lot of code was written, again and again. And what if two applications wanted to access to the same resources ? So, KMS. But why ?

Framebuffer: a buffer in memory, designed to store pixels

The story begins with a plane. Picture it like a group of resources used to create a image. A plane can contains several framebuffers. A big one, to store the full picture, and maybe a small one, something like 64x64 for an hardware cursor ? These framebuffers can be mixed together on the hardware to generate a final framebuffer.

Now, we have a buffer storing our picture. We assigned it to a CRTC (Cathode Ray Tube Controller). A CRTC is directly linked to an ouput. It means if your card has two CRTCs, you can have two different output. Final step, printing something on the screen. A screen is connected using a standard port, HDMI, DVI, VGA… this means encoding our stream to a well defined protocol. That’s it, we have some pixels on our screen !

TTM & GEM

We can print some pixels, great ! But how can we do some fancy 3D stuff ? We have our GL calls going through some mumbo-jumbo stuff, and then what ? How can I actually write something on my GPU’s memory ?

There globally two kind of memory architecture: UMA and dedicated

UMA for Unified Memory Access, is used by Intel Graphics, or on some Android devices. All your memory is accessible from one memory space.
Dedicated memory: You can’t directly access your memory from the CPU.If you want to write it, you have to map a CPU addressable area, write your data, and then, use specific mechanisms to send it on the dedicated memory.

TTM and GEM are two different APIs designed to manage this. TTM is the old one, designed to covering every possible cases. The result is a big and complex interface no sane developer would use. Around 2008, GEM was introduced. A new and lighter API, designed to manage UMA architectures. Nowadays, GEM is often used as a frontend, but when dedicated memory management is needed, TTM is used as backend.

GEM for dummies

The main idea is to link a resource to a GEM handle. Now you only need to tell when a GEM is needed, and memory will be moved on and out our vram. But there is a small problem. To share resources, GEM uses global identifiers. A GEM is linked to a unique, global identifier. This means any program could ask for a specific GEM and get access to the resource… any.

Gladly, we have DMA-BUF. The idea is to link a buffer to a file descriptor. We add some functions to convert a local GEM identifier to a fd, and can safely share our resources.

I’ll stop here for now, but I invite you to check some articles on DMA (Direct memory access) and read this article about TTM & GEM

GSoC 2017 - API Forwarding

Sat, 13 May 2017 00:00:00 +0000

Writing an ICD is a problem in itself. Add to this Windows kernel interfaces, virtIO queues management, resources transfer between host and guest, and BOOM, you are lost. This brings us to our first step: something not efficient but simpler, API Forwarding.

Tasks

Hook OpenGL calls
Serialize function calls
Send them to the miniport-driver, then the host
De-serialize calls and execute them on the host.
Send some data back to the guest

Realization

ICD

The ICD part (Userland) is pretty straightforward. Make your own opengl32.dll, serialize the calls. Now find a sweet function in gdi32.dll to throw your mumbo-jumbo on the kernel side. Fortunately, we have this:

NTSTATUS APIENTRY DxgkDdiEscape(
  _In_ const HANDLE         hAdapter,
  _In_ const DXGKARG_ESCAPE *pEscape
)
{ ... }

A beautiful function available on both DOD and full display driver. It takes a pointer on an userland buffer, and send it to our display driver. Wait… userland buffer, no check, kernel part ? Mmmmm…. What could go wrong ?

Kernel part

To initialize a display driver, you must call a function: DxgkInitialize This function will take a big structure, containing function pointers to your driver. For a display only driver, you will have a reduced set of function to implement. And for a full featured driver, well…

Anyway, now the game is to run the driver, and see where we crash. Sadly we cannot just hope to add some functions, and run only using the working DOD code base. Windows wants something more, and the game is to find what, Yay ! Since we have a working DOD driver, let’s find how we could trick.

ICD <=> Kernel communication

We can register two type of driver: a DOD driver using DxgkInitializeDisplayOnlyDriver and DxgkInitialize. Windows will then know which kind of features each driver can support (fine tune will be done using query callbacks). Both drivers can implement DxgkDdiEscape. Great, we will fool Windows and use this DOD as a fully featured 3D driver ! WRONG !

Setup of the ICD part, sending everything through our escape functions ? check. But return values seams off. After investigation, and any function taking a userland buffer, I came to a conclusion: OpenGL ICD part cannot communicate with a DOD driver. Windows knows we are display only, and fall-back our ICD calls on it’s own driver.

So now, what’s the plan ? Let’s put this problem aside, and try to focus on the real part: create proper commands for the host.

GSoC 2017 - Project presentation

Thu, 11 May 2017 00:00:00 +0000

On my arrival at the lab, I started a little project: working on a display only driver for Windows. A good way to start learning what was hidden under the hood of an OpenGL application. Google Summer of Code 2017 arrived, and subject were published. Among these, QEMU’s ‘Windows Virgl driver’. Great ! Let’s apply !

Applications closed early April. I took a look at the already existing DOD driver (non official repo)

and also decided to learn a bit more about Vulkan. Results came, and I was selected, excellent !

Mission

The idea is to bring 3d acceleration on Windows guests running with QEMU. Using VirtIO devices and Virgl3d.

Context

On this stack, we can work on three parts: opengl32.dll, ICD and Miniport driver.

OpenGL32.dll is just a dynamic library used to communicate with out runtime driver.
ICD: this is the OpenGL implementation. This part is the equivalent of Mesa on Linux.
Miniport-driver: this is the kernel driver. Hardware specific, we are going to do our hypercalls here.

Problems

Windows is not open source. We have some basic ideas about D3DKrnl subsystem behaviour, but nothing is certain.
To develop a complete OpenGL state tracker is a lot of work.
Virgl3D takes some calls, and bytecode for shaders, re-translate it to GLSL, and call OpenGL again. Which means we will do the same work twice. Once on the host, once on the guest.

First steps with Vulkan

Fri, 05 May 2017 00:00:00 +0000

Vulkan is great, vulkan is love, vulkan is $(COMPLIMENT)

I heard a lot about this API, but never took some time to try it… So why not now ? The goal was to do a simple OBJ file viewer. Then, try to improve performances, and of course, since it’s Vulkan, go multithread! The API is pretty simple to use. We fill out some structs, and call a vkSomething function.

Some samples are available in the SDK, and of course, there is this Vulkan-tutorial website.

So commits after commits, the code grew, until the first “Hello, world !”: displaying a white triangle. 1000 lines of code vs 30, that’s quite steep. After some additional 7641 lines, here it us, a simple obj viewer!

GitHub link

But we are the May the 5th, and Google Summer of Code results are out! 🥳 Time to focus on the next big project: OpenGL driver for a Windows on QEMU VMs.

Model time - R5D4

Mon, 06 Feb 2017 00:00:00 +0000

For my upcoming Vulkan project, I needed a model. So here it is ! R5D4, the unchosen droid from Star Wars.

Tools: 3ds Max, Substance Painter, Photoshop

Realtime ocean rendering and buyoancy

Mon, 20 Jun 2016 00:00:00 +0000

My Erasmus took place in Spain, in a city near the coast. So each morning, seeing the sea reminded me how I never tried to work on water rendering.

This article made me want to also work on the buoyancy aspect. And because I was using Unity a lot at that time I decided to create a usable Asset.

Two constraints:

This asset had to work on every model.
It had to be easy to use on every ocean model

Here is the asset (free): ASSET-STORE LINK

And here are some preview:

Model time - Wall-E

Tue, 10 May 2016 00:00:00 +0000

The famous Wall-E for this week’s mini project.

Tools: 3ds Max, Substance Painter, Photoshop

Model time - Snowspeeder

Sat, 07 Nov 2015 00:00:00 +0000

Being a teaching assistant this year. I needed prepare a lab about procedural level generation. Goal for the students: write an infinite “runner” (flyer?). For this occasion, I decided to reproduce a T-47 Snowspeeder from Star Wars.

Tools: 3ds Max, Substance Painter, Photoshop

Multiplayer game - Starfight

Wed, 15 Jul 2015 00:00:00 +0000

In my first year at EPITA, I had an assignment. Create a video-game using Unity. I had 4 weeks, 3 missing teammates, and an idea.

The idea was to combine both the FPS and RTS style in a single multiplayer game.

A game round required 5 players:
The first — through a RTS gameplay — had to protect a central orb.
The other 4 had to seek and destroy the orb the Quake’s fashion.

The RTS side could spawn units, and give movement order. Attack and aim was controller by the AI. The FPS side could fight against these units, or spawn some fixed towers to defend against the units.

The project evaluation was made through presentations. So I decided to create some trailers, and give my teachers an E3-like presentation. Here are these trailers and some screenshots of the game.
Outcome: top promotion.

Technologies: 3ds Max, Unity, Substance Painter, Adobe Premiere, Photoshop, C#

(If somebody at DICE is wondering, yes it is a rip-off of a Battlefront devlog 🙂 )

Rooftop experiment

Thu, 05 Feb 2015 00:00:00 +0000

I was able to use a drone an afternoon. Thus, it was the perfect opportunity to learn more about tracking and mixing real footage with 3D objects. I decided to film one tower at my parent’s farm. Then, create a fictive observatory, and merge everything together.

Tools: After Effect, Boujou, 3ds Max, Photoshop

Art project - Children & Education

Sun, 15 Jun 2014 00:00:00 +0000

Children don’t have the experience a grown up has.

This sentence was the baseline for an art project I worked on during my final year of high school. This book I wrote was one of the three pieces presented on this occasion.

Tools: Adobe Photoshop, Illustrator

Model time - Door

Mon, 05 May 2008 00:00:00 +0000

Let’s go back in time: 2008, when I was 13.
This was one my first serious project. Learning about volumetric lights on

Tools: 3ds Max

Nathan Gauer

Boursorama: auth flow & scraping

Introduction

Step 1: Login

Step 1: Magic cookie the gathering

Step 2: SVG based obfuscation

Step 3: Loggin in!

Step 4: Fetching my data

Final thoughts

Banks, Keypad & Statements

Introduction

The official API

The other API

Step 1: Login

api/login/keypad GET request

api/login POST request

Digit mangling

Getting the transactions

api/login/contract POST request

api/login/contract response.

api/user/accounts GET request

api/user/<account-id>/transactions GET request

Getting old transactions

Final thoughts

Disclosure timeline

Hosting this blog

Sparse virtual textures

Step 1 - Hand-made pagination

Pagination overview

Adding the page concept to the shader

Computing visibility

Rendering pass

Step 2: MipMapping

Step 3: Complex materials

Page request : subsampling, random and frame budget.

Noise, blur and neural networks

The goal

Step 1 - sanity check

Step 3 - Better average - YUV vs RGB

Step 4 - selective average

Step 5 - ML-based noise detection

CTF Write-up: Sogeti 2019 - BadVM

Reversing the VM

Instrumenting using LLDB

Conclusion

3D engine - Parrallax Mapping with self-shadows

Vulkan-ize Virglrenderer - experiment

GSoC 2018 - Vulkan-ize Virglrenderer

The rest of this post contains the same content as the announce email (virgl ML).

Project status

Current behavior

Initialization:

Memory transfers

Commands and execution

Code generation

Issues

1: (Virglrenderer) Vulkan cannot be used next to OpenGL.

2: (Virglrenderer) Command buffers are scattered into several pools

3: (MESA) Vtest and VirtIO switch is not straightforward right now.

4: (Virglrenderer/MESA) vtest error handling is bad.

5: bugs, bugs and bugs.

Next steps

How to test it

Repositories

Vulkan API search engine

Raytracing 2 - KD-Tree and Photons

Raytracing & KD-Trees

Clean output

CAN bus reverse on a Toyota Yaris

Talking with Cars

Press & Seek

Talking with Cars

Raytracing & Pathtracing

GSoC 2017 - 3D acceleration using VirtIOGPU

VirtIO devices

Communication queues

VirGL

OpenGL on Windows

OpenGL State-Tracker

Talk LSE-Week - QEMU and Virgl3D

`api/login/keypad` GET request

`api/login` POST request

`api/login/contract` POST request

`api/login/contract` response.

`api/user/accounts` GET request

`api/user/<account-id>/transactions` GET request