Re: Another security vulnerability

On 4/4/24 4:09 PM, MitchAlsup1 wrote:> Thomas Koenig wrote:
[snip]
 > Given that it is compile time, one either predicts it is taken
 > (loops) or not taken (errors and initialization) and arrange
 > the code such that fall through is the predicted pattern (except
 > for loops).
"Boolean Formula-based Branch Prediction for Future Technologies"
(Daniel A. Jiménez et al., 2001) presents a mechanism for branch
prediction based on a static formula using global history, so *in
theory* a compiler could provide more than just taken/not-taken
predictions. ("Static Methods in Hybrid Branch Prediction", Dirk
Grunwald et al., 1998, proposed static predictor selection,
removing the selector table; Donald Lindsay, the second author of
that paper, had a PhD thesis "Static Methods in Branch Prediction".)
(A static prediction can also be used only for an agree predictor.
It is even conceivable that the dominant direction might not be
the best static agreeing prediction; e.g., if aliases would train
to an agree/disagree state that more often mispredicts the branch
[and the branch has few global entries]. Such would be a very
fragile optimization requiring considerable analysis, so it seems
very unlikely to be practical. [I have wondered if a hash of the
branch address might be XORed with predictor bits to provide a
quasi-tagging. XORing with the prediction could cause the most
interference, good for destructive aliasing; XORing with counter
or hysteresis bits would seem to moderate interfence, allowing a
prediction to be stable such that a selector would tranfer a
mispredicting branch to another table. If an expected/agree sense
was available, such tagging might be more useful.])
 > Then at run time, all these branches are predicted with the standard
 > predictors present in the core.
 > Initialization stuff is mispredicted once or twice
Or not at all if BTB miss generates a correct predict not taken.
(Even without that mechanism, a first encounter might be
correctly predicted by accident.)
 > error code is only mispredicted when an error occurs
 > loops are mispredicted once or twice per entrance.
Or never mispredicted for only-counted loops for which the
counter value is available early enough in the pipeline. (Gshare
can also predict loop exit/entry correctly for small loop counts
with few internal branches. TAGE can do better.)
 > Also note:: With an ISA like My 66000, one can preform branching using
 > predication and neither predict the branch nor modify where FETCH is
 > fetching. Ideally, predication should deal with hard to predict branches
 > and all flow control where the then and else clauses are short. When
 > these are removed from the predictor, prediction should improve--maybe
 > not in the number of predictions that are correct, but in the total time
 > wasted on branching (including both repair and misfetching overheads).
Rarely-executed blocks should presumably use branches even when
short to remove the rarely-executed code from the normal
instruction stream. I would guess that exceptional actions are
typically longer/more complicated.
(Consistent timing would also be important for some real-time
tasks and for avoiding timing side channels.)
The best performing choice would also seem to be potentially
microarchitecture-dependent. Obviously the accuracy of branch
prediction and the cost of aliasing would matter (and
perversely mispredicting a branch can _potentially_ improve
performance, though not on My 66000, I think, because more
persistent microarchitectural state is not updated until
instruction commitment).
If the predicate value is delayed and predicated operations
wait in the scheduler for this operand and the operands of one
path are available before the predicate value, branch prediction
might allow deeper speculation. For highly dynamically
predictable but short branches, deeper speculation might help
more than fetch irregularity hurts. (The predicate could be
predicted — and this prediction is needed later in the pipeline —
but not distinguishing between prediction-allowed predication
and normal predication might prevent prediction from being
implemented to avoid data-dependent timing of predication.)
(The cost of speculation can also be variable. With underutilized
resources (thermal, memory bandwidth, etc.) speculation would
generally be less expensive than with high demand on resources.)